#include <bits/stdc++.h>
using namespace std;
#define int long long int
using pi = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vpi = vector<pi>;
const int INF = 4e18;
struct RMQ {
int n; vector<int> st;
RMQ(int n = 0) : n(n), st(4*n, INF) {}
int update(int i, int l, int r, int k, int v) {
if (!(l <= k && k < r)) return st[i];
if (l+1==r) return st[i] = v;
int m = l + (r-l)/2;
return st[i] = min(update(2*i+1,l,m,k,v),update(2*i+2,m,r,k,v));
}
int query(int i, int l, int r, int ql, int qr) {
if (qr <= l || r <= ql) return -INF;
if (ql <= l && r <= qr) return st[i];
int m = l + (r-l)/2;
return max(query(2*i+1,l,m,ql,qr),query(2*i+2,m,r,ql,qr));
}
int query(int l, int r) {return query(0,0,n,l,r+1);}
void update(int k, int v) {update(0,0,n,k,v);}
};
/*
sliding window of edges of length k
... -> ... -> ... ->
choose intermediate nodes
dp[start][end][start s][end t] = min(dp[start][mid][s][mid2] + dp[mid][end][mid2][t]) over all mid, mid2
so its literally floyd warshall if he was good
can do one query in o(logn) with rmq
so o(k^3 log(n)) per start, end
but its just binary lifting ish so just do o(k^3 log^2(n) n)
dp[start][inc][s][t]
*/
int k, n, m, o;
int dp[50'000][17][5][5] = {};
void minplus(int start[5][5], int mid[5][5], int end[5][5]) {
for (int x = 0; x < k; x++) {
for (int y = 0; y < k; y++) {
for (int z = 0; z < k; z++) {
end[x][y] = min(end[x][y], start[x][z] + mid[z][y]);
}
}
}
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
cin >> k >> n >> m >> o;
for (int i = 0; i < 50'000; i++) for (int j = 0; j < 17; j++) for (int k = 0; k < 5; k++) for (int l = 0; l < 5; l++) dp[i][j][k][l] = INF;
for (int i = 0; i < m; i++) {
int a, b, w; cin >> a >> b >> w;
dp[a/k][0][a%k][b%k] = w;
}
for (int bit = 1; bit < 17; bit++) {
for (int i = 0; i+(1<<(bit-1)) < (n+k-1)/k; i++) {
minplus(dp[i][bit-1], dp[i + (1<<(bit-1))][bit-1], dp[i][bit]);
}
}
while (o--) {
int a, b; cin >> a >> b;
int start = a/k, end = b/k;
int v[5][5]; for (int i = 0; i < k; i++) for (int j = 0; j < k; j++) v[i][j] = INF;
for (int i = 0; i < k; i++) v[i][i] = 0;
int dist = end - start;
for (int j = 16; j >= 0; j--) {
if ((1<<j) > dist) continue;
int t[5][5]; for (int i = 0; i < k; i++) for (int j = 0; j < k; j++) t[i][j] = INF;
minplus(v, dp[start][j], t);
swap(v, t);
start += 1<<j; dist -= 1<<j;
}
cout << (v[a % k][b % k] == INF ? -1 : v[a % k][b % k]) << '\n';
}
return 0;
}
