#include <bits/stdc++.h>
using namespace std;
int const N=2e5;
int const inf=1e9+5;
int wei[N][20][6];
int main(){
int k,n,m,o;
cin>>k>>n>>m>>o;
for(int i=0;i<n;i++)
for(int j=0;j<=16;j++)
for(int kk=0;kk<=5;kk++)
wei[i][j][kk]=inf;
for(int i=0;i<m;i++){
int a,b,w;
cin>>a>>b>>w;
// swap(a,b);//switch directions;
wei[a][0][b%k]=w;
}
//compute
int midnode=0;
for(int par=1;par<=15;par++){
for(int node=0;node<n;node++){
midnode=(((1<<(par-1))+(node/k))*k);
for(int md=0;md<k;md++){
for(int d=0;d<k;d++){
wei[node][par][md]=min(wei[node][par][md],(wei[node][par-1][d]+wei[midnode+d][par-1][md]));
}
}
}
}
while(o--){
int a,b;
cin>>a>>b;
int d=(b/k)-(a/k);
if(d<0){
cout<<-1<<endl;
continue;
}
int w[k],ww[k];
for(int i=0;i<k;i++)
w[i]=inf;
w[a%k]=0;
int cur=a/k;
while(d){
int par=31-(__builtin_clz(d));
d-=(1<<par);
// cout<<"par "<<par<<endl;
for(int i=0;i<k;i++){
int mn=inf;
for(int j=0;j<k;j++)
mn=min(mn,w[j]+wei[(cur*k)+j][par][i]);
ww[i]=mn;
}
for(int i=0;i<k;i++)
w[i]=ww[i];
cur+=(1<<par);
}
if(w[b%k]>=inf)
w[b%k]=-1;
cout<<w[b%k]<<endl;
}
return 0;
}
