#include <bits/stdc++.h>
#define DIM 50010
#define INF 2000000000
using namespace std;
int k,n,m,q,i,j,x,y,el,cost,nr;
int aint[DIM*4][6][6],sol[6][6],aux[6][6],intv[DIM][6][6];
vector <pair<int,int> > L[DIM];
void init (int a[][6]){
for (int i=0;i<k;i++)
for (int j=0;j<k;j++)
a[i][j] = INF;
}
void build (int nod, int st, int dr){
if (st == dr){
/// practic eu in nod tin minte costul sa ajung din st in st+1
for (int i=st*k;i<min((st+1)*k,n);i++){
for (auto it:L[i]){
int j = it.first, cost = it.second;
aint[nod][i%k][j%k] = min(aint[nod][i%k][j%k],cost);
}
}
return;
}
int mid = (st+dr)>>1;
build (nod<<1,st,mid);
build ((nod<<1)|1,mid+1,dr);
int fiu_st = nod<<1, fiu_dr = (nod<<1)|1;
/// vr sa combin doua intervale, st mid si mid+1 dr
/// costul de ajung din st in dr+1!!
for (int i=0;i<k;i++)
for (int j=0;j<k;j++)
for (int t=0;t<k;t++)
if (aint[fiu_st][i][t] != INF && aint[fiu_dr][t][j] != INF)
aint[nod][i][j] = min (aint[nod][i][j],aint[fiu_st][i][t] + aint[fiu_dr][t][j]);
}
void query (int nod, int st, int dr, int x, int y){
if (x <= st && dr <= y){
el++;
for (int i=0;i<k;i++)
for (int j=0;j<k;j++)
intv[el][i][j] = aint[nod][i][j];
return;
}
int mid = (st+dr)>>1;
if (x <= mid)
query (nod<<1,st,mid,x,y);
if (y > mid)
query ((nod<<1)|1,mid+1,dr,x,y);
}
int main (){
//ifstream cin ("date.in");
//ofstream cout ("date.out");
cin>>k>>n>>m>>q;
for (i=1;i<=m;i++){
cin>>x>>y>>cost;
L[x].push_back(make_pair(y,cost));
}
nr = (n-1)/k;
for (i=1;i<=4*nr;i++)
init (aint[i]);
build (1,0,nr);
for (;q--;){
cin>>x>>y;
if (x/k >= y/k){
cout<<-1<<"\n";
continue;
}
el = 0;
query (1,0,nr,x/k,y/k-1);
/// pt primul interval un rest il am deja stabilit
init(sol);
//for (i=0;i<k;i++)
// sol[x%k][i] = intv[1][x%k][i];
for (int i=0;i<k;i++)
for (int j=0;j<k;j++)
sol[i][j] = intv[1][i][j];
for (int idx=2;idx<=el;idx++){
init (aux);
for (int i=0;i<k;i++)
for (int j=0;j<k;j++)
for (int t=0;t<k;t++)
if (sol[i][t] != INF && intv[idx][t][j] != INF)
aux[i][j] = min (aux[i][j],sol[i][t] + intv[idx][t][j]);
for (int i=0;i<k;i++)
for (int j=0;j<k;j++)
sol[i][j] = aux[i][j];
}
if (sol[x%k][y%k] == INF)
cout<<-1<<"\n";
else cout<<sol[x%k][y%k]<<"\n";
}
return 0;
}
