#include <bits/stdc++.h>
using namespace std;
#define F0R(i, n) for (ll i= 0 ; i< n;i++)
#define FOR(i,j,n) for (ll i = j; i< n;i++)
template<typename T>
using V = vector<T>;
using ll = long long;
using vi = V<ll>;
using pi = pair<ll,ll>;
ll k, n, m, o;
constexpr ll INF = 1e9 + 7;
V<V<vi>> base;
V<vi> combine(V<vi> a, V<vi> b) {
V<vi> c(k, vi(k, INF));
F0R(i, k) {
F0R(j, k) {
F0R(l, k) {
c[i][l] = min(c[i][l], a[i][j] + b[j][l]);
}
}
}
return c;
}
struct Seg
{
Seg *left = nullptr, *right = nullptr;
ll l, r, mid;
V<vi> to;
Seg(ll l, ll r) : l(l), r(r), mid((l + r) / 2) {
if (r -l > 1) {
left = new Seg(l, mid);
right = new Seg(mid, r);
to = combine(left->to, right->to);
} else {
to = base[l];
}
}
V<vi> q(ll a, ll b) {
if (b <= l or a >= r) return {};
if (a<=l and b>= r) {
return to;
}
auto r1 = left->q(a,b);
auto r2 = right->q(a,b);
if (r1.empty()) return r2;
if (r2.empty()) return r1;
return combine(r1, r2);
}
};
int main() {
cin >> k >> n >> m >> o;
base.resize((n + 1) / k, V<vi>(k, vi(k, INF)));
F0R(i, m) {
ll a, b, c; cin >> a >> b >> c;
base[a / k][a % k][b % k] = c;
}
Seg* seg = new Seg(0, (n +1) / k);
F0R(i, o) {
ll a, b; cin >> a >> b;
auto r = seg->q(a / k, b / k);
if (r.empty() or r[a % k][b % k] >= INF)
cout << "-1" << "\n";
else {
cout << r[a % k][b % k] << "\n";
}
}
}
