#include<bits/stdc++.h>
#define pb emplace_back
#define AI(i) begin(i), end(i)
using namespace std;
using ll = long long;
template<class T>
bool chmax(T &val, T nv) { return val < nv ? (val = nv, true) : false; }
template<class T>
bool chmin(T &val, T nv) { return nv < val ? (val = nv, true) : false; }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() {cerr << endl;}
template<class T1, class ...T2>
void kout (T1 v, T2 ...e) { cerr << v << ' ', kout(e...); }
template<class T>
void debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L)==R], ++L; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
// What I should check
// 1. overflow
// 2. corner cases
// Enjoy the problem instead of hurrying to AC
// Good luck !
const int MAX_N = 50010, inf = 1e9, MAX_K = 5, MAX_L = 16;
int k, n, m, q;
#pragma GCC optimize("Ofast")
int dp[MAX_L][MAX_N][MAX_K][MAX_K];
int32_t main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> k >> n >> m >> q;
for (int i = 0;i < MAX_L;++i) for (int j = 0;j < n;++j) for (int l = 0;l < k;++l) for (int m = 0;m < k;++m)
dp[i][j][l][m] = inf;
for (int a, b, t, i = 0;i < m;++i) {
cin >> a >> b >> t;
dp[0][a / k][a % k][b % k] = t;
}
for (int d = 1;1 << d <= n;++d) {
for (int i = 0;i < n / k;++i)
for (int j = 0;j < k;++j) for (int l = 0;l < k;++l)
for (int m = 0;m < k;++m)
chmin(dp[d][i][j][m], dp[d-1][i][j][l] + dp[d-1][i + (1<<(d-1))][l][m]);
}
auto qry = [&](int a, int b) {
if (a / k == b / k) return -1;
int dis = b / k - a / k;
int *mat = new int[k], *tmp = new int[k];
for (int i = 0;i < k;++i) mat[i] = inf;
mat[a % k] = 0;
for (int d = 0;1 << d <= dis;++d) if (dis >> d & 1) {
DE(d);
fill(tmp, tmp + k, inf);
for (int i = 0;i < k;++i) for (int j = 0;j < k;++j) {
chmin(tmp[j], mat[i] + dp[d][a / k][i][j]);
}
a += (1 << d) * k;
swap(tmp, mat);
}
return mat[b % k] == inf ? -1 : mat[b % k];
};
while (q--) {
int a, b;
cin >> a >> b;
cout << qry(a, b) << '\n';
}
}
