#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e14;
vector<vector<ll>> multiply(const vector<vector<ll>> &A, const vector<vector<ll>> &B, int k) {
vector<vector<ll>> C(k, vector<ll>(k, INF));
for (int i = 0; i < k; i++) {
for (int j = 0; j < k; j++) {
for (int s = 0; s < k; s++) {
C[i][j] = min(C[i][j], A[i][s] + B[s][j]);
}
}
}
return C;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int k, a, m, q;
cin >> k >> a >> m >> q;
int blocks = (a + k - 1) / k;
vector<vector<vector<ll>>> mat(blocks, vector<vector<ll>>(k, vector<ll>(k, INF)));
for (int i = 0; i < blocks; i++){
for (int j = 0; j < k; j++){
mat[i][j][j] = 0;
}
}
for (int i = 0; i < m; i++){
ll x, y, t;
cin >> x >> y >> t;
ll bx = x / k, by = y / k;
if (by == bx + 1) {
mat[bx][x % k][y % k] = min(mat[bx][x % k][y % k], t);
}
}
int L = floor(log2(blocks)) + 1;
vector<vector<vector<vector<ll>>>> st(blocks, vector<vector<vector<ll>>>(L, vector<vector<ll>>(k, vector<ll>(k, INF))));
for (int i = 0; i < blocks; i++){
st[i][0] = mat[i];
}
for (int l = 1; l < L; l++){
for (int i = 0; i + (1 << l) <= blocks; i++){
st[i][l] = multiply(st[i][l-1], st[i + (1 << (l-1))][l-1], k);
}
}
while(q--){
ll x, y;
cin >> x >> y;
ll bx = x / k, by = y / k;
if (bx == by) {
cout << -1 << "\n";
continue;
}
vector<vector<ll>> res(k, vector<ll>(k, INF));
for (int i = 0; i < k; i++){
res[i][i] = 0;
}
int idx = bx;
int remain = by - bx;
for (int p = L - 1; p >= 0; p--){
if ((1 << p) <= remain) {
res = multiply(res, st[idx][p], k);
idx += (1 << p);
remain -= (1 << p);
}
}
ll ans = res[x % k][y % k];
if (ans >= INF) cout << -1 << "\n";
else cout << ans << "\n";
}
return 0;
}
