#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;
const int NMAX = 5e4;
const int RMAX = 5;
const int LOGMAX = 16;
const int INF = 1e9;
int k, n, m, q;
int dp[NMAX + 1][LOGMAX + 1][RMAX + 1][RMAX + 1];
void combine(int c[RMAX + 1][RMAX + 1], int a[RMAX + 1][RMAX + 1], int b[RMAX + 1][RMAX + 1]) {
for(int i = 0; i < RMAX; i++) {
for(int j = 0; j < RMAX; j++) {
c[i][j] = INF;
for(int k = 0; k < RMAX; k++) {
c[i][j] = min(c[i][j], a[i][k] + b[k][j]);
}
}
}
}
int query(int A, int B) {
int a = A / k;
int x = A % k;
int b = B / k;
int y = B % k;
if (a > b) return -1;
int dist = b - a;
int c[RMAX + 1][RMAX + 1];
for(int i = 0; i < RMAX; i++) {
for(int j = 0; j < RMAX; j++) {
c[i][j] = (i == j) ? 0 : INF;
}
}
int curr = a;
for(int i = 0; (1 << i) <= dist; i++) {
if(dist >> i & 1) {
int cc[RMAX + 1][RMAX + 1];
combine(cc, c, dp[curr][i]);
for(int j1 = 0; j1 < RMAX; j1++) {
for(int j2 = 0; j2 < RMAX; j2++) {
c[j1][j2] = cc[j1][j2];
}
}
curr += (1 << i);
}
}
return (c[x][y] == INF ? -1 : c[x][y]);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> k >> n >> m >> q;
for(int i = 0; i <= n / k; i++) {
for(int j = 0; j <= LOGMAX; j++) {
for(int r1 = 0; r1 < RMAX; r1++) {
for(int r2 = 0; r2 < RMAX; r2++) {
dp[i][j][r1][r2] = INF;
}
}
}
}
for(int i = 1; i <= m; i++) {
int a, b, c;
cin >> a >> b >> c;
dp[a / k][0][a % k][b % k] = c;
}
int lim = n / k;
for(int p = 1; (1 << p) <= lim; p++) {
for(int i = 0; i + (1 << p) <= lim; i++) {
combine(dp[i][p], dp[i][p - 1], dp[i + (1 << (p - 1))][p - 1]);
}
}
while(q--) {
int a, b;
cin >> a >> b;
cout << query(a, b) << '\n';
}
return 0;
}
