#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll>pairll;
typedef pair<ll,pairll>pairlll;
typedef pair<pairll,pairll>pairllll;
typedef long double ld;
typedef pair<ll,string>pairls;
#define INF 1000000000000007
#define MOD 1000000007
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
ll k,n,m,o,res[10007],t[50007][7];
vector<pairll>v[50007];
struct D{
ll l,r,q;
}d[10007];
bool mcp(D d1, D d2){
return d1.l<d2.l;
}
int main() {
cin>>k>>n>>m>>o;
for(int i=1;i<=m;i++){
ll l,r,c;
cin>>l>>r>>c;
v[r].pb({l,c});
}
for(int i=1;i<=o;i++){
cin>>d[i].l>>d[i].r;
d[i].q=i;
}
sort(d+1,d+1+o,mcp);
ll x=0;
for(int i=1;i<=o;i++){
if(d[i].l/k!=d[i-1].l/k || i==1){
x=d[i].l-d[i].l%k;
for(int j=0;j<k;j++){
t[x][j]=t[x+1][j]=t[x+2][j]=t[x+3][j]=t[x+4][j]=INF;
}
t[x][0]=t[x+1][1]=t[x+2][2]=t[x+3][3]=t[x+4][4]=0;
for(int j=x+k;j<n;j++){
for(int y=0;y<k;y++){
t[j][y]=INF;
for(auto it: v[j]){
t[j][y]=min(t[j][y],t[it.fr][y]+it.sc);
}
}
}
}
if(d[i].l>d[i].r || t[d[i].r][d[i].l%k]==INF)res[d[i].q]=-1;
else res[d[i].q]=t[d[i].r][d[i].l%k];
}
for(int i=1;i<=o;i++){
cout<<res[i]<<endl;
}
}
