#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int mxn = 3e5 + 10;
const int LOG = 20;
int ans[6][6], tmp[6][6];
int dp[mxn][LOG][6][6];
int k, n, m, q;
void ono_min(int &s, int t) {
if(s > t) s = t;
}
int box(int u) {
return u / k;
}
void build() {
for(int i = 1; i <= LOG; i++) {
for(int Lbox = 0; Lbox <= box(n - 1); Lbox++) {
int Mbox = Lbox + (1 << (i - 1));
int Rbox = Lbox + (1 << i);
if(Rbox > box(n - 1)) continue;
for(int l = 0; l < k; l++)
for(int r = 0; r < k; r++)
for(int m = 0; m < k; m++)
ono_min(dp[Lbox][i][l][r], dp[Lbox][i - 1][l][m] + dp[Mbox][i - 1][m][r]);
// cout << " > " << Lbox << ' ' << Rbox << '\n';
// for(int l = 0; l < k; l++)
// for(int r = 0; r < k; r++) {
// int Lnode = Lbox * k + l;
// int Rnode = Rbox * k + r;
// cout << Lnode << ' ' << Rnode << ": " << dp[Lbox][i][l][r] << '\n';
// }
}
}
}
int main() {
cin >> k >> n >> m >> q;
for(int i = 0; i <= box(n - 1); i++)
for(int j = 0; j < LOG; j++)
for(int l = 0; l < k; l++)
for(int r = 0; r < k; r++)
dp[i][j][l][r] = inf;
for(int i = 0; i < m; i++) {
int s, f, t;
cin >> s >> f >> t;
dp[box(s)][0][s % k][f % k] = t;
}
build();
while(q--) {
int Lnode, Rnode;
cin >> Lnode >> Rnode;
for(int i = 0; i < k; i++)
for(int j = 0; j < k; j++)
ans[i][j] = inf;
for(int i = 0; i < k; i++)
ans[i][i] = 0;
int Lbox = box(Lnode), Rbox = box(Rnode);
for(int lg = LOG - 1; lg >= 0; lg--) {
if(Lbox + (1 << lg) <= Rbox) {
for(int i = 0; i < k; i++)
for(int j = 0; j < k; j++)
tmp[i][j] = inf;
for(int i = 0; i < k; i++)
for(int j = 0; j < k; j++)
for(int m = 0; m < k; m++)
ono_min(tmp[i][j], ans[i][m] + dp[Lbox][lg][m][j]);
for(int i = 0; i < k; i++)
for(int j = 0; j < k; j++) {
// int Lnode = Lbox * k + i;
// int Rnode = Rbox * k + j;
// cout << Lnode << ' ' << Rnode << ": " << tmp[i][j] << '\n';
ans[i][j] = tmp[i][j];
}
Lbox += (1 << lg);
}
}
cout << ((ans[Lnode % k][Rnode % k] == inf) ? -1 : ans[Lnode % k][Rnode % k]) << '\n';
}
return 0;
}
