#include <iostream>
using namespace std;
struct MATRIX {
long long int a[5][5];
MATRIX() {
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
a[i][j] = 999999999;
}
}
}
};
MATRIX f[50005][18];
MATRIX mul(MATRIX a, MATRIX b){
MATRIX res;
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
res.a[i][j] = 999999999;
for (int k = 0; k < 5; k++) {
res.a[i][j] = min(res.a[i][j], a.a[i][k] + b.a[k][j]);
}
}
}
return res;
}
int main() {
int n, k, m, q;
cin >> k >> n >> m >> q;
for (int i = 1; i <= m; i++) {
int a, b, t;
cin >> a >> b >> t;
f[a / k][0].a[a % k][b % k] = t;
}
for (int i = 1; (1 << i) <= n; i++){
for (int j = 0; j + (1 << i) - 1 <= n; j++) {
f[j][i] = mul(f[j][i - 1], f[j + (1 << (i - 1))][i - 1]);
}
}
for (int jj = 0; jj < q; jj++) {
int a, b;
cin >> a >> b;
MATRIX s;
for (int j = 0; j < 5; j++) {
s.a[j][j] = 0;
}
if (a == b) {
cout << 0 << endl;
continue;
}
int h = a / k, g = b / k;
if (g <= h) {
cout << -1 << endl;
}
else {
int l = g - h;
for (int j = 16; j >= 0; j--) {
if (l & (1 << j)) {
s = mul(s, f[h][j]);
h += (1 << j);
}
}
if (s.a[a % k][b % k] == 999999999) cout << -1 << endl;
else cout << s.a[a % k][b % k] << endl;
}
}
}
