#include <bits/stdc++.h>
using namespace std;
int k,n,m,o;
long long d[50001][16][6][6];
void read()
{
cin>>k>>n>>m>>o;
for(int b=0;b<=(n-1)/k;b++)
for(int i1=0;i1<k;i1++)
for(int i2=0;i2<k;i2++)
d[b][0][i1][i2]=1e9;
for(int i=1;i<=m;i++)
{
int a,b;
long long t;
cin>>a>>b>>t;
int b1=a/k;
int i1=a%k;
int i2=b%k;
d[b1][0][i1][i2]=min(d[b1][0][i1][i2],t);
}
}
void prec()
{
for(int lg=1;lg<16;lg++)
for(int i1=0;i1<k;i1++)
for(int i2=0;i2<k;i2++)
for(int b=0;b<=(n-1)/k;b++)
{
d[b][lg][i1][i2]=1e9;
for(int i3=0;i3<k;i3++)
d[b][lg][i1][i2]=min(d[b][lg-1][i1][i3]
+d[min(49999,b+(1<<(lg-1)))][lg-1][i3][i2],
d[b][lg][i1][i2]);
}
}
long long ans[8],ans2[8];
void compute(int a,int b)
{
for(int i=0;i<k;i++)
ans[i]=1e9;
ans[a%k]=0;
int jump=b/k-a/k;
int block=a/k;
for(int lg=0;lg<16;lg++)
{
if((1<<lg)&jump)
{
for(int i=0;i<k;i++)
ans2[i]=ans[i];
for(int i2=0;i2<k;i2++)
{
ans[i2]=1e9;
for(int i1=0;i1<k;i1++)
ans[i2]=min(ans[i2],ans2[i1]+d[block][lg][i1][i2]);
}
block+=(1<<lg);
}
}
int i=b%k;
if(ans[i]>=1e9)cout<<-1<<endl;
else cout<<ans[i]<<endl;
}
void solve()
{
for(int i=1;i<=o;i++)
{
int a,b;
cin>>a>>b;
compute(a,b);
}
}
int main() {
read();
prec();
solve();
return 0;
}
