#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
#include <bits/stdc++.h>
#define ar array
using namespace std;
using ll = long long;
const ll INF = 1LL<<60;
const int mxN = 5e4;
ar<ll, 5> g[mxN];
int mnNxt[mxN];
ll ans[mxN+10];
int main() {
ios::sync_with_stdio(0);cin.tie(0);
int k, n, m, q; cin >> k >> n >> m >> q;
cerr << k << '\n';
for (int i = 0; i < n; ++i)
for (int d = 0; d < k; ++d)
g[i][d] = INF;
for (int mm = 0; mm < m; ++mm) {
int i, j, w; cin >> i >> j >> w;
g[i][j%k] = w;
}
for (int i = 0; i < n; ++i)
mnNxt[i] = i/k*k+k;
fill(ans, ans+n+10, INF);
for (int qq = 0; qq < q; ++qq) {
int i, j; cin >> i >> j;
for (int p = j+1; p < n; ++p)
ans[p] = INF;
ans[j] = 0;
for (int p = j-1; p >= i; --p) {
ans[p] = INF;
for (int d = 0; d < k; ++d)
ans[p] = min(ans[mnNxt[p]+d]+g[p][d], ans[p]);
}
if (ans[i] > INF/2) cout << "-1\n";
else cout << ans[i] << '\n';
}
}
