#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define pb push_back
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
using Matrix = array<array<int, 5>, 5>;
Matrix id;
for(int i=0; i<5; i++){
for(int j=0; j<5; j++){
if(i != j) id[i][j] = 1e9;
else id[i][j] = 0;
}
}
auto mult = [&](Matrix A, Matrix B){
Matrix C;
for(int i=0; i<5; i++){
for(int j=0; j<5; j++){
C[i][j] = 1e9;
for(int k=0; k<5; k++){
C[i][j] = min(C[i][j], A[i][k] + B[k][j]);
}
}
}
return C;
};
int k, n, m, q;
cin >> k >> n >> m >> q;
n = (n-1)/k;
Matrix to[n][18];
for(int j=0; j<=17; j++){
for(int i=0; i<n; i++){
for(int x=0; x<5; x++){
for(int y=0; y<5; y++) to[i][j][x][y] = 1e9;
}
}
}
while(m--){
int a, b, t; cin >> a >> b >> t;
int c = a/k, d = b/k;
to[c][0][a-k*c][b-k*d] = t;
}
for(int j=1; j<=17; j++){
for(int i=0; i+(1<<j)<=n; i++){
to[i][j] = mult(to[i][j-1], to[i+(1<<(j-1))][j-1]);
}
}
while(q--){
int a, b; cin >> a >> b;
int c = a/k, d = b/k;
if(c >= d){
cout << -1 << "\n";
continue;
}
int y = d-c;
Matrix C = id;
for(int j=17; j>=0; j--){
if(y & (1<<j)){
C = mult(C, to[c][j]);
c = c+(1<<j);
}
}
c = a/k;
int ans = C[a-k*c][b-k*d];
if(ans == 1e9) ans = -1;
cout << ans << "\n";
}
}
