#include <bits/stdc++.h>
typedef long long ll;
const ll inf = 1e15;
const ll N = 50001;
const ll K = 5;
ll adj[N][K];
ll n, k;
struct Node {
std::vector<std::vector<ll>> arr;
ll tl = -1, tr = -1;
Node() {}
};
bool operator==(const Node &a, const Node &b) { return a.arr == b.arr; }
class SegmentTree {
public:
std::vector<Node> seg;
ll n;
SegmentTree(ll n) {
this->n = n;
seg.resize(4 * n);
}
Node idt() { return Node(); }
Node f(const Node &a, const Node &b) {
if (a == idt()) {
return b;
}
if (b == idt()) {
return a;
}
Node ret;
ret.tl = a.tl, ret.tr = b.tr;
auto &ans = ret.arr;
ans = std::vector<std::vector<ll>>(k, std::vector<ll>(k, inf));
for (ll s = 0; s < k; ++s) {
for (ll e = 0; e < k; ++e) {
for (ll s1 = 0; s1 < k; ++s1) {
for (ll e1 = 0; e1 < k; ++e1) {
if (k * a.tr + s1 > ::n) {
continue;
}
ans[s][e] =
std::min(ans[s][e],
a.arr[s][s1] + adj[k * a.tr + s1][e1] + b.arr[e1][e]);
}
}
}
}
return ret;
}
void construct(ll v, ll tl, ll tr) {
if (tl == tr) {
seg[v] = Node();
seg[v].tl = tl, seg[v].tr = tr;
seg[v].arr = std::vector<std::vector<ll>>(k, std::vector<ll>(k, inf));
for (ll i = 0; i < k; ++i) {
seg[v].arr[i][i] = 0;
}
} else {
ll tm = (tl + tr) / 2;
construct(2 * v, tl, tm);
construct(2 * v + 1, tm + 1, tr);
seg[v] = f(seg[2 * v], seg[2 * v + 1]);
}
}
void construct() { construct(1, 0, n); }
Node query(ll v, ll tl, ll tr, ll l, ll r) {
if (tl > tr || l > r || tr < l || r < tl) {
return idt();
}
if (l <= tl && tr <= r) {
return seg[v];
}
ll tm = (tl + tr) / 2;
return f(query(2 * v, tl, tm, l, r), query(2 * v + 1, tm + 1, tr, l, r));
}
Node query(ll l, ll r) { return query(1, 0, n, l, r); }
};
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
ll m, o;
std::cin >> k >> n >> m >> o;
for (ll i = 0; i < n; ++i) {
for (ll j = 0; j < k; ++j) {
adj[i][j] = inf;
}
}
for (ll i = 0, a, b, t; i < m; ++i) {
std::cin >> a >> b >> t;
adj[a][b - a - (k - (a % k))] = t;
}
SegmentTree tree(n);
tree.construct();
while (o--) {
ll a, b;
std::cin >> a >> b;
auto q = tree.query(a / k, b / k);
ll ans = q.arr[a % k][b % k];
std::cout << (ans == inf ? -1 : ans) << '\n';
}
}
