#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// #define int long long
const int N=5e4+1000;
vector<pair<int,int>> ma[N];
// int ans[6][6];
// int ans_[6][6];
int n,k;
struct Data
{
int mat[6][6];
int block=0;
Data()
{
for(int i=0;i<6;i++)
{
for(int j=0;j<6;j++)
{
mat[i][j]=1e9;
}
}
}
Data(int x)
{
for(int i=0;i<6;i++)
{
for(int j=0;j<6;j++)
{
mat[i][j]=x*(i!=j);
}
}
}
void print()
{
cout<<"Start\n";
for(int i=0;i<6;i++)
{
for(int l=0;l<6;l++)
{
cout<<mat[i][l]<<' ';
}
cout<<endl;
}
cout<<"Finish\n";
cout<<"Block "<<block<<endl;
}
};
Data* seg[N*8];
Data* merge(Data* a,Data* b)
{
Data* ans=new Data();
// cout<<"Merge "<<a->block<<' '<<b->block<<endl;
for(int l=0;l<6;l++)
{
for(int i=0;i<6;i++)
{
// for(int j=0;j<6;j++)
// {
// for(auto& [l,w]:ma[(a->block*k)+j])
// {
// ans->mat[j][l%k]=min(ans->mat[j][l%k],a->mat[i][j]+b->mat[j][l%k]+w);
// }
// }
// cout<<"From "<<l<<" to "<<i<<' '<<a->mat[l][i]<<endl;
for(auto& [j,w]:ma[(a->block*k)+i])
{
for(int p=0;p<6;p++)
{
// cout<<"For "<<
ans->mat[l][p]=min(ans->mat[l][p],a->mat[l][i]+w+b->mat[j%k][p]);
}
}
}
}
ans->block=b->block;
// cout<<"APDS\n";
return ans;
}
void build(int v=1,int s=0,int e=(n-1)/k)
{
// cout<<s<<' '<<e<<' '<<v<<endl;
if(s==e)
{
seg[v]=new Data(1e9);
seg[v]->block=s;
// cout<<"Leaf "<<s<<endl;
// seg[v]->print();
return;
}
int lc=(2*v);
int rc=lc+1;
int mid=(s+e)/2;
build(lc,s,mid);
build(rc,mid+1,e);
seg[v]=new Data();
seg[v]=merge(seg[lc],seg[rc]);
// cout<<"For range "<<s<<' '<<e<<endl;
// seg[v]->print();
}
Data* get(int l,int r,int v=1,int s=0,int e=(n-1)/k)
{
// if(r<s or e<l)
// {
// Data* ap=new Data(0);
// return ap;
// }
Data* ap;
if(l<=s and e<=r)
{
ap=seg[v];
}
else
{
int lc=(2*v);
int rc=lc+1;
int mid=(s+e)/2;
if(s<=r and mid>=l)
{
ap=get(l,r,lc,s,mid);
if((mid+1)<=r and e>=l)
{
ap=merge(ap,get(l,r,rc,mid+1,e));
}
}
else
{
if((mid+1)<=r and e>=l)
{
ap=get(l,r,rc,mid+1,e);
}
}
}
if(ap==NULL)
exit(-1);
return ap;
}
signed main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int m,q;
cin>>k>>n>>m>>q;
for(int j=0;j<m;j++)
{
int a,b,t;
cin>>a>>b>>t;
ma[a].push_back({b,t});
}
// for(int lp=0;lp<q;lp++)
// {
// int x,y;
// cin>>x>>y;
// query[x].push_back({y,lp});
// }
// for(int i=0;i<n;i++)
// {
// index[i]=block[i/k].size();
// block[(i/k)].push_back(i);
// }
// for(int l=0;l<n;l++)
// for(int ind=0;ind<k;ind++)
// for(int p=0;p<k;p++)
// Dist[l][ind][p]=1e9;
// for(int i=0;i<n;i++)
// Dist[(i/k)][i%k][i%k]=we;
build();
for(int lp=0;lp<q;lp++)
{
int x,y;
cin>>x>>y;
int cur_block=x/k;
int block_to=y/k;
Data* apl=get(cur_block,block_to);
int ansp=apl->mat[x%k][y%k];
if(ansp==1e9)
{
cout<<-1<<'\n';
}
else
{
cout<<ansp<<'\n';
}
}
return 0;
}
