#include<bits/stdc++.h>
using namespace std;
int k,n,m,o;
constexpr int inf=1000000000;
struct Mat{
vector<vector<int>>a;
Mat(){
a.assign(k,vector<int>(k,inf));
}
Mat(const vector<vector<int>>&b):a(b){}
friend Mat operator*(const Mat&a,const Mat&b){
Mat c=Mat();
for(int i=0;i<k;i++)for(int j=0;j<k;j++)for(int l=0;l<k;l++)c.a[i][j]=min(c.a[i][j],a.a[i][l]+b.a[l][j]);
return c;
}
static const Mat e(){
Mat c=Mat();
for(int i=0;i<k;i++)c.a[i][i]=0;
return c;
}
};
struct segtree{
private:
int n;
vector<Mat>seg;
public:
segtree(int n):n(n){seg.assign(2*n,Mat::e());}
segtree(const vector<Mat>&v){
n=v.size();
seg.assign(2*n,Mat::e());
for(int i=0;i<n;i++)seg[i+n]=v[i];
for(int i=n-1;i>0;i--)seg[i]=seg[i<<1]*seg[i<<1|1];
}
Mat prod(int l,int r)const{
Mat sml=Mat::e(),smr=Mat::e();
for(l+=n,r+=n;l<r;l>>=1,r>>=1){
if(l&1)sml=sml*seg[l++];
if(r&1)smr=seg[--r]*smr;
}
return sml*smr;
}
};
int main(){
cin>>k>>n>>m>>o;
vector<Mat>mat(n/k);
for(int i=0;i<m;i++){
int a,b,c;cin>>a>>b>>c;
mat[a/k].a[a%k][b%k]=min(mat[a/k].a[a%k][b%k],c);
}
segtree seg(mat);
while(o--){
int a,b;cin>>a>>b;
auto res=seg.prod(a/k,b/k);
//for(int i=0;i<k;i++)for(int j=0;j<k;j++)cout<<res.a[i][j]<<" \n"[j==k-1];
int ans=res.a[a%k][b%k];
if(ans==inf)ans=-1;
cout<<ans<<endl;
}
}
