#include <bits/stdc++.h>
#define int long long
using namespace std;
int k, a, b, c;
int z[100005][5][5]; // Lưu thông tin chuyển tiếp giữa các khối
int bruh = 1e16;
vector<vector<int>> f[400005];
// Hàm combine 2 ma trận từ 2 đoạn liên tiếp
vector<vector<int>> combine(vector<vector<int>> left, vector<vector<int>> right, int mid) {
vector<vector<int>> res(k, vector<int>(k, bruh));
for (int i = 0; i < k; i++) {
for (int j = 0; j < k; j++) {
for (int l = 0; l < k; l++) {
for (int r = 0; r < k; r++) {
res[i][j] = min(res[i][j], left[i][l] + z[mid][l][r] + right[r][j]);
}
}
}
}
return res;
}
// Xây dựng cây phân đoạn trên các khối từ l đến r (các chỉ số của khối)
void build(int id, int l, int r) {
f[id].resize(k, vector<int>(k, bruh));
if (l == r) {
for (int i = 0; i < k; i++) {
f[id][i][i] = 0;
}
return;
}
int mid = (l + r) / 2;
build(id * 2, l, mid);
build(id * 2 + 1, mid + 1, r);
f[id] = combine(f[id * 2], f[id * 2 + 1], mid);
}
// Hàm truy vấn trên cây phân đoạn: trả về ma trận tổng hợp cho đoạn [x, y]
vector<vector<int>> get(int id, int l, int r, int x, int y) {
vector<vector<int>> full(k, vector<int>(k, bruh));
// Nếu đoạn [l, r] không giao với [x, y]
if (x > r || y < l) {
return full;
}
// Nếu đoạn [l, r] nằm hoàn toàn trong [x, y]
if (x <= l && r <= y) {
return f[id];
}
int mid = (l + r) / 2;
vector<vector<int>> pre1 = get(id * 2, l, mid, x, y);
vector<vector<int>> pre2 = get(id * 2 + 1, mid + 1, r, x, y);
// Nếu một trong hai ma trận trả về là ma trận full (không giao nhau), trả về ma trận còn lại
if (pre1 == full) return pre2;
if (pre2 == full) return pre1;
return combine(pre1, pre2, mid);
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> k >> a >> b >> c;
// Khởi tạo mảng z với giá trị bruh (vô cực) cho tất cả các chỉ số
for (int i = 0; i < 10005; i++) {
for (int j = 0; j < k; j++) {
for (int t = 0; t < k; t++) {
z[i][j][t] = bruh;
}
}
}
// Đọc các cạnh giữa các đỉnh, ánh xạ vào khối và vị trí trong khối
for (int i = 1; i <= b; i++) {
int x, y, t;
cin >> x >> y >> t;
// x/k: chỉ số khối, x%k: vị trí trong khối; tương tự với y
z[x / k][x % k][y % k] = t;
}
int n = a / k + 1; // số khối trong đồ thị
build(1, 0, n - 1); // xây dựng cây phân đoạn với phạm vi [0, n-1]
for (int i = 1; i <= c; i++) {
int x, y;
cin >> x >> y;
int sta = x / k;
int fin = y / k;
// Nếu điểm xuất phát và đích nằm cùng 1 khối, theo quy định không có đường hợp lệ
if (sta == fin) {
cout << -1 << "\n";
continue;
}
vector<vector<int>> r = get(1, 0, n - 1, sta, fin);
if (r[x % k][y % k] >= bruh) {
cout << -1 << "\n";
} else {
cout << r[x % k][y % k] << "\n";
}
}
return 0;
}
