#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 10;
const int T = 270;
const int inf = 1e9 + 7;
int k, n, m, q, dp[N][T];
vector<pair<int, int>> g[N];
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> k >> n >> m >> q;
for (int i = 0; i < m; i ++){
int a, b, t;
cin >> a >> b >> t;
g[a].push_back({t, b});
}
for (int i = n - 1; i >= 0; i --){
for (int j = 0; j < T; j ++)
dp[i][j] = inf;
dp[i][0] = 0;
for (auto [w, u] : g[i]){
int d = u - i;
dp[i][d] = w;
for (int j = 1; j < T; j ++){
int ud = (i + j) - u;
if (ud < 0) continue;
dp[i][j] = min(dp[i][j], w + dp[u][ud]);
}
}
}
for (int i = 0; i < q; i ++){
int a, b;
cin >> a >> b;
assert(a < b);
int d = b - a;
vector<pair<int, int>> vec;
vec.push_back({0, a});
int cur = a;
while (d >= T){
vector<pair<int, int>> nxt;
for (int j = 9; j > 0; j --){
int v = cur + T - j;
int best = inf;
for (auto [dist, u] : vec)
best = min(best, dist + dp[u][v - u]);
if (best == inf) continue;
nxt.push_back({best, v});
}
vec = nxt;
int dist = T - 9;
if (nxt.size())
dist = nxt[0].second - cur;
cur += dist;
d -= dist;
}
int ans = inf;
for (auto [dist, v] : vec){
int d = b - v;
if (d < 0 or d >= T) continue;
ans = min(ans, dist + dp[v][d]);
}
if (ans >= inf)
ans = -1;
cout << ans << '\n';
}
}
