#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct adjmat {
ll adj[5][5];
adjmat() {
for (int i = 0 ; i < 5; i++){
for (int j = 0; j < 5; j++) {
adj[i][j] = 1e12;
}
}
}
};
adjmat combine(adjmat a, adjmat b) {
adjmat cur;
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
if (a.adj[i][j] != 0) {
for (int k = 0; k < 5; k++) {
cur.adj[i][k] = min(cur.adj[i][k], a.adj[i][j] + b.adj[j][k]);
}
}
}
}
return cur;
}
struct node {
int l, r;
adjmat adj;
node *lc, *rc;
node(int _l, int _r) {
l = _l, r = _r;
if (l == r) return;
int mid = (l + r) / 2;
lc = new node(l, mid);
rc = new node(mid + 1, r);
}
void upd(int group, int ql, int qr, ll cost) {
if (l == r) {
adj.adj[ql][qr] = min(adj.adj[ql][qr], cost);
return;
}
int mid = (l + r) / 2;
if (group <= mid) lc->upd(group, ql, qr, cost);
else rc->upd(group, ql, qr, cost);
adj = combine(lc->adj, rc->adj);
}
adjmat query(int ba, int a, int bb, int b) {
if (ba <= l && r <= bb) return adj;
int mid = (l + r) / 2;
if (bb <= mid) return lc->query(ba, a, bb, b);
if (ba > mid) return rc->query(ba, a, bb, b);
return combine(lc->query(ba, a, bb, b), rc->query(ba, a, bb, b));
}
};
int main() {
int k, n, m, o; cin >> k >> n >> m >> o;
node *root = new node(0, n);
for (int i = 0; i < m; i++) {
int a, b, t; cin >> a >> b >> t;
int ga = a / k, gb = b / k;
root->upd(ga, a % k, b % k, t);
}
for (int i = 0; i < o; i++) {
int a, b; cin >> a >> b;
if (a / k >= b/ k) {
cout << -1 << "\n"; continue;
}
assert(a/k <= b/k-1);
adjmat bruh = root->query(a / k, a % k, b / k - 1, b % k);
cout <<( bruh.adj[a % k][b %k] >= 1e10 ? -1 : bruh.adj[a % k][b % k]) << "\n";
}
}
