#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int k, n, m, q;
cin >> k >> n >> m >> q;
vector<pair<int, int>> E[n];
while (m--) {
int x, y, w;
cin >> x >> y >> w;
E[y].push_back({x, w});
}
while (q--) {
int x, y;
cin >> x >> y;
if (x > y) {
cout << "-1\n";
continue;
}
vector<int> dp(y - x + 1, (int)1e9);
dp[0] = 0;
for (int i = x + 1; i <= y; i++) {
for (auto [j, w] : E[i])
if (x <= j) dp[i - x] = min(dp[i - x], dp[j - x] + w);
}
cout << (dp[y - x] == (int)1e9 ? -1 : dp[y - x]) << '\n';
}
}
