#include <bits/stdc++.h>
using namespace std;
#define pb push_back
//#define int long long
const int maxN = 4e5 + 7;
vector<pair<int, int>> g[maxN];
int dp[maxN];
void solve() {
int k, n, m, o;
cin >> k >> n >> m >> o;
for(int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
g[v].pb({u, w});
}
while(o--) {
int a, b;
cin >> a >> b;
int pa = a, ob = b;
for(int i = a; i <= b; i++) dp[i] = 1e9;
dp[a] = 0;
a /= k;
b /= k;
for (int i = a + 1; i <= b; i++) {
int l = i * k;
int r = min(n - 1, l + k - 1);
for (int v = l; v <= r; v++) {
for (auto [u, w] : g[v]) {
if (u >= pa && u <= ob && dp[u] != 1e9) {
dp[v] = min(dp[v], dp[u] + w);
}
}
}
}
if(dp[ob] == 1e9) cout << -1 << '\n';
else cout << dp[ob] << '\n';
}
}
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//freopen("input.txt", "r", stdin);
int t = 1;
//cin >> t;
while(t--) solve();
}
