#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 5e4 + 5;
array<array<int, 5>, 5> st[maxn][17];
array<array<int, 5>, 5> merge(array<array<int, 5>, 5> a, array<array<int, 5>, 5> b){
array<array<int, 5>, 5> res;
for(int i = 0; i < 5; i++) for(int j = 0; j < 5; j++) res[i][j] = 1e15;
for(int i = 0; i < 5; i++){
for(int j = 0; j < 5; j++){
for(int k = 0; k < 5; k++) res[i][j] = min(res[i][j], a[i][k] + b[k][j]);
}
}
return res;
}
void solve(){
for(int i = 0; i < maxn; i++){
for(int j = 0; j < 17; j++){
for(int k = 0; k < 5; k++){
for(int l = 0; l < 5; l++) st[i][j][k][l] = 1e15;
}
}
}
int k, n, m, o; cin >> k >> n >> m >> o;
for(int i = 1; i <= m; i++){
int a, b, t; cin >> a >> b >> t;
st[a / k][0][a % k][b % k] = t;
}
for(int j = 1; j <= 16; j++){
for(int i = 0; i + (1 << (j - 1)) <= n / k; i++){
st[i][j] = merge(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
}
while(o--){
int a, b; cin >> a >> b;
int x = a / k, y = b / k;
array<array<int, 5>, 5> res;
for(int i = 0; i < 5; i++){
for(int j = 0; j < 5; j++){
res[i][j] = 1e15;
}
res[i][i] = 0;
}
for(int j = 16; j >= 0; j--){
if(x + (1 << j) <= y){
res = merge(res, st[x][j]);
x += (1 << j);
}
}
cout << (res[a % k][b % k] == 1e15 ? -1 : res[a % k][b % k]) << "\n";
}
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
solve();
}
