#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T>
using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const ll M = 998244353;
// const ll M = 1e9 + 7;
#define all(v) (v).begin(), (v).end()
#define ff first
#define ss second
const ll INFL = 1e18;
const int INF = 1e9;
int lift[17][50000][5];
void solve() {
int K, N, M, O;
cin >> K >> N >> M >> O;
for (int i=0; i<17; i++) {
for (int j=0; j<N; j++) {
for (int k=0; k<K; k++) {
lift[i][j][k] = 1e9;
}
}
}
for (int i=0; i<M; i++) {
int a, b, t;
cin >> a >> b >> t;
lift[0][a][b%K] = t;
}
for (int sz=1; sz<17; sz++) {
for (int a=0; a<N; a++) {
for (int to=0; to<K; to++) {
for (int m=0; m<K; m++) {
int b = (a-(a%K))+(1<<(sz-1))*K+m;
if (b>=N) break;
lift[sz][a][to] = min(lift[sz][a][to], lift[sz-1][a][m]+lift[sz-1][b][to]);
}
}
}
}
while (O--) {
int a, b;
cin >> a >> b;
int d = ((b-(b%K))-(a-(a%K)))/K;
if (d==0) {
cout << "-1\n";
continue;
}
int mn[5];
int nxt[5];
for (int i=0; i<K; i++) mn[i] = 1e9;
mn[a%K] = 0;
int cur = a-(a%K);
for (int i=0; i<17; i++) {
if (!(d>>i&1)) continue;
for (int j=0; j<K; j++) nxt[j] = 1e9;
for (int j=0; j<K; j++) {
for (int k=0; k<K; k++) {
nxt[k] = min(nxt[k], mn[j]+lift[i][cur+j][k]);
}
}
cur += (1<<i)*K;
d -= 1<<i;
for (int j=0; j<K; j++) {
mn[j] = nxt[j];
}
}
int ans = mn[b%K];
if (ans != 1e9) cout << ans << '\n';
else cout << "-1\n";
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(NULL);
int tc = 1;
// cin >> tc;
while (tc--) solve();
}
