#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const int N = 5e4 + 5;
const int oo = 1e18 + 7, mod = 1e9 + 7;
int k, n, m, q;
vector<ii> Adj[N];
int dist[N][555];
int mn_dist[N];
void process(){
cin >> k >> n >> m >> q;
for(int i = 1; i <= m; i++){
int u, v, w;
cin >> u >> v >> w;
Adj[v].pb({u, w});
}
for(int i = 0; i < n; i++){
for(int j = i + 1; j <= min(n - 1, i + 550); j++){
dist[i][j - i] = oo;
for(auto it : Adj[j]){
if(it.fi < i) continue;
dist[i][j - i] = min(dist[i][j - i], dist[i][it.fi - i] + it.se);
}
}
}
while(q--){
int u, v;
cin >> u >> v;
int temp1 = u / k, temp2 = v / k;
if(temp1 >= temp2){
cout << "-1\n";
continue;
}
for(int i = temp1 * k; i < (temp1 + 1) * k; i++) mn_dist[i] = oo;
mn_dist[u] = 0;
for(; temp1 < (temp2 - 100); temp1 += 100){
for(int i = (temp1 + 100) * k; i < (temp1 + 101) * k; i++) mn_dist[i] = oo;
for(int i = (temp1 + 100) * k; i < (temp1 + 101) * k; i++){
for(int j = temp1 * k; j < (temp1 + 1) * k; j++) mn_dist[i] = min(mn_dist[i], mn_dist[j] + dist[j][i - j]);
}
}
//cout << temp1 << " " << u << " " << v << "\n";
//continue;
mn_dist[v] = oo;
for(int i = temp1 * k; i < (temp1 + 1) * k; i++) mn_dist[v] = min(mn_dist[v], mn_dist[i] + dist[i][v - i]);
cout << (mn_dist[v] == oo ? -1 : mn_dist[v]) << "\n";
}
}
signed main(){
ios_base::sync_with_stdio(0);
process();
}
