#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int k, n, m, q;
cin >> k >> n >> m >> q;
int g = (n + k - 1) / k;
int go[g][16][k][k];
for (int i = 0; i < g; i++) {
for (int b = 0; b < 16; b++) {
for (int c = 0; c < k; c++) {
for (int d = 0; d < k; d++) {
go[i][b][c][d] = 1e9;
}
}
}
}
for (int i = 0; i < m; i++) {
int a, b, w;
cin >> a >> b >> w;
go[a / k][0][a % k][b % k] = w;
}
for (int b = 1; (1 << b) < g; b++) {
for (int i = 0; i < g; i++) {
if (i + (1 << b) > g - 1) break;
for (int c = 0; c < k; c++) {
for (int d = 0; d < k; d++) {
for (int mid = 0; mid < k; mid++) {
go[i][b][c][d] = min(go[i][b][c][d], go[i][b - 1][c][mid] + go[i + (1 << (b - 1))][b - 1][mid][d]);
}
}
}
}
}
while (q--) {
int a, b;
cin >> a >> b;
int x = a / k, y = b / k;
int d = y - x;
vector<vector<int>> dp(k, vector<int>(k, 1e9));
for (int i = 0; i < k; i++) {
dp[i][i] = 0;
}
for (int b = 0; (1 << b) <= d; b++) {
if (d & (1 << b)) {
vector<vector<int>> dq(k, vector<int>(k, 1e9));
for (int to = 0; to < k; to++) {
for (int from = 0; from < k; from++) {
for (int mid = 0; mid < k; mid++) {
dq[from][to] = min(dq[from][to], dp[from][mid] + go[x][b][mid][to]);
}
}
}
swap(dp, dq);
x += 1 << b;
}
}
int ans = dp[a % k][b % k];
cout << (ans == 1e9 ? -1 : ans) << '\n';
}
}
