/*input
5 14 5 5
0 5 9
5 12 10
0 7 7
7 12 8
4 7 10
0 12
0 5
0 7
7 12
0 13
*/
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
#define REP(i,n) for(int i=0;i<n;i++)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
#define pii pair<int,int>
#define pb push_back
#define f first
#define ll long long
#define s second
const int INF=0x3f3f3f3f;
const ll INF64=4e18;
struct node{
ll dist[5][5];
}seg[4*maxn];
inline node merge(node a,node b){
node c;
REP(i,5) REP(j,5) c.dist[i][j]=INF64;
REP(k,5){
REP(i,5){
REP(j,5){
MNTO(c.dist[i][j],a.dist[i][k]+b.dist[k][j]);
}
}
}
return c;
}
inline void upd(int idx,int l,int r,int p,int i,int j,int x){
if(r<p or l>p) return;
if(l==r){
seg[idx].dist[i][j]=x;
return;
}
int mid=(l+r)/2;
upd(idx*2,l,mid,p,i,j,x);
upd(idx*2+1,mid+1,r,p,i,j,x);
//seg[idx]=merge(seg[idx*2],seg[idx*2+1]);
}
inline void mrg(int idx,int l,int r){
if(l==r) return;
int mid=(l+r)/2;
mrg(idx*2,l,mid);
mrg(idx*2+1,mid+1,r);
seg[idx]=merge(seg[idx*2],seg[idx*2+1]);
}
inline node query(int idx,int l,int r,int ql,int qr){
//node c;
//REP(i,5) REP(j,5) c.dist[i][j]=0;
//if(r<ql or l>qr) return c;
if(ql<=l and r<=qr) return seg[idx];
int mid=(l+r)/2;
if(mid<ql) return query(idx*2+1,mid+1,r,ql,qr);
if(mid>=qr) return query(idx*2,l,mid,ql,qr);
return merge(query(idx*2,l,mid,ql,qr),query(idx*2+1,mid+1,r,ql,qr));
}
int main(){
ios::sync_with_stdio(false),cin.tie(0);
int k,n,m,q;
cin>>k>>n>>m>>q;
REP(i,4*n) REP(j,5) REP(k,5) seg[i].dist[j][k]=INF64;
REP(i,m){
int a,b,c;
cin>>a>>b>>c;
upd(1,0,(n/k),a/k,a%k,b%k,c);
}
mrg(1,0,(n/k));
REP(i,q){
int a,b;
cin>>a>>b;
if((a/k)>=(b/k)){
cout<<"-1\n";
continue;
}
node z=query(1,0,(n/k),a/k,b/k-1);
ll x=z.dist[a%k][b%k];
if(x==INF64) x=-1;
cout<<x<<'\n';
}
}
