//alternativ cu rmq, aceasi complexitate
#include<iostream>
#include<vector>
using namespace std;
vector<pair<int,int> > A[50005],Qu[50005];
int k,DpSt[50005][7][7],DpDr[50005][7][7],Rez[10005];
pair<int,int> Q[10005];
void solve(int st, int dr)
{
if(st==dr)
{
for(auto qu:Qu[st])
{
if(qu.first!=st)
continue;
if(Q[qu.second].first==Q[qu.second].second)
Rez[qu.second]=0;
}
return;
}
int mij=(st+dr)/2;
for(int i=st; i<=mij; i++)
for(int j=0; j<k; j++)
for(int ind=0; ind<k; ind++)
DpSt[i][j][ind]=1000000000;
for(int i=mij; i<=dr; i++)
for(int j=0; j<k; j++)
for(int ind=0; ind<k; ind++)
DpDr[i][j][ind]=1000000000;
for(int i=0; i<k; i++)
DpSt[mij][i][i]=DpDr[mij][i][i]=0;
for(int i=mij; i<dr; i++)
{
for(int j=0; j<k; j++) //la mij am fost in j
{
for(int ind=0; ind<k; ind++) //la i am fost in ind
{
for(auto other:A[i*k+ind])
DpDr[i+1][j][other.first%k]=min(DpDr[i+1][j][other.first%k],DpDr[i][j][ind]+other.second);
}
}
}
for(int i=mij-1; i>=st; i--)
{
for(int j=0; j<k; j++)
{
for(int ind=0; ind<k; ind++)
{
for(auto other:A[i*k+ind])
DpSt[i][j][ind]=min(DpSt[i][j][ind],DpSt[i+1][j][other.first%k]+other.second);
}
}
}
for(int i=st; i<=mij; i++)
{
for(auto qu:Qu[i])
{
if(qu.first<=mij || qu.first>dr)
continue;
for(int j=0; j<k; j++)
Rez[qu.second]=min(Rez[qu.second],DpSt[i][j][Q[qu.second].first%k]+DpDr[qu.first][j][Q[qu.second].second%k]);
}
}
solve(st,mij);
solve(mij+1,dr);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n,q,m;
cin>>k>>n>>m>>q;
for(int i=1; i<=m; i++)
{
int x,y,t;
cin>>x>>y>>t;
A[x].push_back({y,t});
}
for(int i=1; i<=q; i++)
{
int x,y;
cin>>x>>y;
Q[i]={x,y};
Qu[x/k].push_back({y/k,i});
Rez[i]=1000000000;
}
solve(0,n/k);
for(int i=1; i<=q; i++)
{
if(Rez[i]==1000000000)
cout<<"-1\n";
else
cout<<Rez[i]<<"\n";
}
return 0;
}
