#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
const int N = 5e4, inf = 1e9;
struct Node {
int a[5][5];
Node() {
for (int i = 0; i < 5; ++i) {
for (int j = 0; j < 5; ++j) {
a[i][j] = inf;
}
}
}
Node operator + (const Node &o) const {
Node res;
for (int i = 0; i < 5; ++i) {
for (int j = 0; j < 5; ++j) {
for (int k = 0; k < 5; ++k) {
res.a[i][k] = min(res.a[i][k], a[i][j] + o.a[j][k]);
}
}
}
return res;
}
};
int k, n, m, o;
int c[N][5];
Node s[4 * N];
vector<array<int, 2>> g[N];
void bld(int id = 1, int l = 0, int r = n / k - 1) {
if (l == r) {
for (int i = 0; i < k; ++i) {
int ii = l * k + i;
for (int j = 0; j < k; ++j) {
s[id].a[i][j] = !c[ii][j] ? inf : c[ii][j];
}
}
return;
}
int m = (l + r) / 2;
bld(id * 2, l, m);
bld(id * 2 + 1, m + 1, r);
s[id] = s[id * 2] + s[id * 2 + 1];
}
Node qry(int u, int v, int id = 1, int l = 0, int r = n / k - 1) {
if (u <= l && r <= v) {
return s[id];
}
int m = (l + r) / 2;
if (v <= m) {
return qry(u, v, id * 2, l, m);
}
if (m < u) {
return qry(u, v, id * 2 + 1, m + 1, r);
}
return qry(u, v, id * 2, l, m) + qry(u, v, id * 2 + 1, m + 1, r);
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> k >> n >> m >> o;
while (m--) {
int a, b, w; cin >> a >> b >> w;
c[a][b % k] = w;
}
bld();
while (o--) {
int a, b; cin >> a >> b;
if (a / k == b / k) {
cout << -1 << "\n";
} else {
auto d = qry(a / k, b / k - 1);
int res = d.a[a % k][b % k];
cout << (res == inf ? -1 : res) << "\n";
}
}
return 0;
}
