#include <bits/stdc++.h>
#include <cassert>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 50505
#define MAXS 17
#define INF 10000000000000
#define bb ' '
#define ln '\n'
#define Ln '\n'
#define MK 5
vector<vector<ll>> sp[MAX][MAXS];
int K;
vector<vector<ll>> operator+(vector<vector<ll>>& v1, vector<vector<ll>>& v2) {
vector<vector<ll>> res = vector<vector<ll>>(K, vector<ll>(K, INF));
int i, j, k;
for (i = 0; i < K; i++) for (j = 0; j < K; j++) for (k = 0; k < K; k++) res[i][j] = min(res[i][j], v1[i][k] + v2[k][j]);
return res;
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
int N, M, Q;
cin >> K >> N >> M >> Q;
int i, j;
int X = (N + K - 1) / K;
for (i = 0; i < MAX; i++) for (j = 0; j < MAXS; j++) sp[i][j] = vector<vector<ll>>(K, vector<ll>(K, INF));
int a, b, c;
for (i = 1; i <= M; i++) {
cin >> a >> b >> c;
sp[a / K][0][a % K][b % K] = c;
}
for (j = 1; j < MAXS; j++) for (i = 0; i <= X; i++) if (i + (1 << (j - 1)) <= X + 1) sp[i][j] = sp[i][j - 1] + sp[i + (1 << (j - 1))][j - 1];
while (Q--) {
cin >> a >> b;
int aa = a;
int d = b / K - a / K;
a /= K;
vector<vector<ll>> v;
for (i = 0; i < MAXS; i++) {
if (d >> i & 1) {
if (v.empty()) v = sp[a][i];
else v = v + sp[a][i];
a += 1 << i;
}
}
ll ans = v[aa % K][b % K];
if (ans >= INF) cout << -1 << ln;
else cout << ans << ln;
}
}
