#include<bits/stdc++.h>
using namespace std;
struct query { int l,r,pos; };
const int MAXN=5e4+5;
const int INF=1e9;
vector< pair<int,int> > ds[MAXN],sd[MAXN];
int ans[MAXN],dpl[MAXN][5],dpr[MAXN][5];
void dnc(int l,int r,int k,vector<query> vq)
{
if(l==r)
{
for(auto v:vq) ans[v.pos]=-1;
return ;
}
int mid=(l+r)/2;
priority_queue< pair<int,int>,vector< pair<int,int> >,greater< pair<int,int> > > pq,qp;
for(int i=l*k;i<(r+1)*k;i++) for(int j=0;j<5;j++) dpl[i][j]=dpr[i][j]=INF;
for(int i=mid*k;i<(mid+1)*k;i++)
{
int res=i%k;
dpl[i][res]=dpr[i][res]=0,qp.push({0,i}),pq.push({0,i});
while(!pq.empty())
{
int a=pq.top().first,b=pq.top().second;
pq.pop();
if(dpr[b][res]<a) continue;
for(auto v:ds[b]) if(dpr[v.first][res]>a+v.second) pq.push({dpr[v.first][res]=a+v.second,v.first});
}
while(!qp.empty())
{
int a=qp.top().first,b=qp.top().second;
qp.pop();
if(dpl[b][res]<a) continue;
for(auto v:sd[b]) if(dpl[v.first][res]>a+v.second) qp.push({dpl[v.first][res]=a+v.second,v.first});
}
}
vector<query> vl,vr;
for(auto v:vq) if((mid+1)*k<=v.l) vr.push_back(v);
else if(v.r<(mid+1)*k) vl.push_back(v);
else
{
int a=INF;
for(int j=0;j<k;j++) a=min(a,dpl[v.l][j]+dpr[v.r][j]);
if(a==INF) ans[v.pos]=-1;
else ans[v.pos]=a;
}
dnc(l,mid,k,vl);
dnc(mid+1,r,k,vr);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int k,n,m,q;
cin>>k>>n>>m>>q;
for(int i=1;i<=m;i++)
{
int l,r,v;
cin>>l>>r>>v;
ds[l].push_back({r,v}),sd[r].push_back({l,v});
}
vector<query> vq;
for(int i=1;i<=q;i++)
{
int l,r;
cin>>l>>r;
vq.push_back({l,r,i});
}
dnc(0,(n-1)/k,k,vq);
for(int i=1;i<=q;i++) cout<<ans[i]<<"\n";
}
