#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 50005;
int K, D[MAX_N][5][5];
const int INF = 5e8 + 5;
void chmin(int& a, int b) {
a = a < b ? a : b;
}
struct segment_tree {
struct node {
int DP[5][5], nxt[5][5];
node() {
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
DP[i][j] = nxt[i][j] = INF;
}
}
}
};
node merge(node& a, node& b) {
node c;
memcpy(c.nxt, b.nxt, sizeof b.nxt);
for (int s1 = 0; s1 < K; s1++)
for (int t1 = 0; t1 < K; t1++)
for (int s2 = 0; s2 < K; s2++)
for (int t2 = 0; t2 < K; t2++)
chmin(c.DP[s1][t2], a.DP[s1][t1] + a.nxt[t1][s2] + b.DP[s2][t2]);
return c;
}
int size;
vector<node> tree;
segment_tree(int n) : size(2 << __lg(n)), tree(4 << __lg(n)) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < 5; j++) {
tree[size + i].DP[j][j] = 0;
}
}
for (int i = 0; i < n; i++) {
memcpy(tree[size + i].nxt, D[i], sizeof D[i]);
}
for (int i = size - 1; i > 0; i--) {
tree[i] = merge(tree[i * 2], tree[i * 2 + 1]);
}
}
node query(int l, int r) {
return query(l, r + 1, 1, 0, size);
}
node query(int l, int r, int x, int lx, int rx) {
if (lx >= l && rx <= r) {
return tree[x];
} else {
int mid = (lx + rx) / 2;
if (mid > l && mid < r) {
node left = query(l, r, x * 2, lx, mid);
node right = query(l, r, x * 2 + 1, mid, rx);
return merge(left, right);
} else if (mid > l) {
return query(l, r, x * 2, lx, mid);
} else {
return query(l, r, x * 2 + 1, mid, rx);
}
}
}
};
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int N, M, Q;
cin >> K >> N >> M >> Q;
for (int i = 0; i < N; i++) {
for (int j = 0; j < 5; j++) {
for (int k = 0; k < 5; k++) {
D[i][j][k] = INF;
}
}
}
for (int i = 0; i < M; i++) {
int A, B, T;
cin >> A >> B >> T;
D[A / K][A % K][B % K] = T;
}
segment_tree tree((N + K - 1) / K);
while (Q--) {
int A, B;
cin >> A >> B;
if (A / K < B / K) {
segment_tree::node value = tree.query(A / K, B / K);
cout << (value.DP[A % K][B % K] >= INF ? -1 : value.DP[A % K][B % K]) << "\n";
} else {
cout << -1 << "\n";
}
}
}
