#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long int ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vvll> vvvll;
typedef vector<vvvll> vvvvll;
int K, N, M, O;
int levs;
vvvvll dp;
ll func(int levi, int i, int k, int j, int l){
if (levi+(1<<k)>=levs) return 1e18;
return dp[levi][i][k][l]+dp[levi+(1<<k)][l][k][j];
}
void ini(){
for (int k=1; k<20; k++){
for (int levi=0; levi<levs-1; levi++){
for (int i=0; i<K; i++){
for (int j=0; j<K; j++){
for (int l=0; l<K; l++){
dp[levi][i][k][j]=min(dp[levi][i][k][j], func(levi,i,k-1,j,l));
}
}
}
}
}return;
}
ll binlift(int a, int b){
int act=a/5, fin=b/5;
vector<ll>res(K, 1e18);
res[a%K]=0;
for (int k=19; k>=0; k--){
if (act+(1<<k)<fin){
vector<ll>aux(K, 1e18);
for (int i=0; i<K; i++){
for (int j=0; j<K; j++) aux[i]=min(aux[i], res[j]+dp[act][j][k][i]);
}swap(res, aux);
act=act+(1<<k);
}
}
ll ans=1e18;
for (int i=0; i<K; i++) ans=min(ans, res[i]+dp[act][i][0][b%K]);
if (ans==1e18) return -1;
else return ans;
}
int main(){
cin>>K>>N>>M>>O;
levs=ceil(N/K);
dp.assign(levs, vvvll(K, vvll(20, vll(K, 1e18))));
for (int i=0; i<M; i++){
int a, b; ll t;
cin>>a>>b>>t;
dp[a/K][a%K][0][b%K]=t;
}
ini();
while (O--){
int a, b;
cin>>a>>b;
cout<<binlift(a, b)<<'\n';
}
return 0;
}
