#include<bits/stdc++.h> #define rep(a,b,c) for(ll a=b;a<=c;++a) #define ll long long #define ff first #define ss second #define mp make_pair using namespace std; typedef pair<int,int> pii; typedef pair<ll,ll> pll; const ll N=5e4+5,inf=1e18; ll n,m,k,q,ans[N],dis[5][N]; vector<pll> adj_pos[N],adj_opp[N]; vector<pair<pll,ll> > QQ; ll left(ll x){return x*k;} ll right(ll x){return min(n-1,x*k+k-1);} ll ID(ll x){return x/k;} void dij(ll start,vector<pll> *adj,ll *dis,ll L,ll R){ rep(i,L,R) dis[i]=inf; dis[start]=0; priority_queue<pll,vector<pll>,greater<pll> > pq; pq.push(mp(0,start)); while(!pq.empty()){ ll u=pq.top().ss,cost=pq.top().ff;pq.pop(); if(cost>dis[u]) continue; for(auto o:adj[u]){ ll v=o.ff,w=o.ss; if(!(L<=v&&v<=R)) continue; if(dis[u]+w<dis[v]){ dis[v]=dis[u]+w; pq.push(mp(dis[v],v)); } } } } void DC(ll l,ll r,vector<pair<pll,ll> > &qry){ if(l==r){ for(auto o:qry){ ll L=o.ff.ff,R=o.ff.ss,id=o.ss; ans[id]=-1; } return ; } ll mid=(l+r)>>1; rep(i,left(mid),right(mid)){ dij(i,adj_opp,dis[i-left(mid)],left(l),right(mid-1)); dij(i,adj_pos,dis[i-left(mid)],left(mid+1),right(r)); } vector<pair<pll,ll> > lft,rgt; for(auto o:qry){ ll L=o.ff.ff,R=o.ff.ss,id=o.ss; if(ID(L)>mid) rgt.push_back(o); else if(ID(R)<=mid) lft.push_back(o); else{ ans[id]=inf; rep(i,0,k-1) ans[id]=min(ans[id],dis[i][L]+dis[i][R]); if(ans[id]==inf) ans[id]=-1; } } vector<pair<pll,ll> >().swap(qry); DC(l,mid,lft); DC(mid+1,r,rgt); } signed main(){ ios::sync_with_stdio(0);cin.tie(0); cin>>k>>n>>m>>q; rep(i,1,m){ ll u,v,w; cin>>u>>v>>w; adj_pos[u].push_back(mp(v,w)); adj_opp[v].push_back(mp(u,w)); } rep(i,1,q){ ll u,v; cin>>u>>v; QQ.push_back(mp(mp(u,v),i)); } DC(0,n/k,QQ); rep(i,1,q) cout<<ans[i]<<'\n'; return 0; }