#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 50'000 + 5;
const int MAX_LG = 16;
const int MAX_K = 5;
const int INF = 1e9;
int k, n, m, o, dp[MAX_LG][MAX_N][MAX_K];
int main() {
cin >> k >> n >> m >> o;
for (int i = 0; i < MAX_LG; ++i) {
for (int j = 0; j < MAX_N; ++j) {
fill(dp[i][j], dp[i][j] + MAX_K, INF);
}
}
for (int e = 0, a, b, t; e < m; ++e) {
cin >> a >> b >> t;
dp[0][a][b % k] = t;
}
n = (n + k - 1) / k * k;
for (int i = 1; i < MAX_LG; ++i) {
for (int u = (n / k - (1 << i)) * k - 1; u >= 0; --u) {
for (int j = 0; j < k; ++j) {
for (int l = 0; l < k; ++l) {
dp[i][u][j] = min(dp[i][u][j], dp[i - 1][u][l] + dp[i - 1][(u / k + (1 << (i - 1))) * k + l][j]);
}
}
}
}
while (o--) {
int a, b;
cin >> a >> b;
int curr[k], nxt[k];
fill(curr, curr + k, INF);
curr[a % k] = 0;
for (int i = 0, d = b / k - a / k, st = a / k * k; d != 0; ++i, d >>= 1) {
if (d & 1) {
fill(nxt, nxt + k, INF);
for (int j = 0; j < k; ++j) {
for (int l = 0; l < k; ++l) {
nxt[j] = min(nxt[j], curr[l] + dp[i][st + l][j]);
}
}
for (int j = 0; j < k; ++j) {
curr[j] = nxt[j];
}
st += (1 << i) * k;
}
}
if (curr[b % k] == INF) {
cout << "-1\n";
} else {
cout << curr[b % k] << '\n';
}
}
}
