#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using llu=unsigned long long;
using ll=long long;
using ld=long double;
using pir=pair<ll,ll>;
using vl=vector<ll>;
using sl=set<ll>;
using msl=multiset<ll>;
using prq=priority_queue<ll>;
using prqi=priority_queue<ll,vector<ll>,greater<ll>>;
using ma=map<ll,ll>;
using vp=vector<pair<ll,ll>>;
using vvl=vector<vector<ll>>;
using vvvl=vector<vector<vector<ll>>>;
using vvp=vector<vector<pair<ll,ll>>>;
using sp=set<pair<ll,ll>>;
using msp=multiset<pair<ll,ll>>;
#define nfs string::npos
#define count1(n) __builtin_popcountll(n)
#define last1(n) __builtin_ctzll(n)
#define first1(n) 63-__builtin_clzll(n)
#define maxi(v) max_element(all(v))
#define mini(v) min_element(all(v))
#define lb(n) lower_bound(n)
#define ub(n) upper_bound(n)
#define lbd(v,n) lower_bound(all(v),n)
#define ubd(v,n) upper_bound(all(v),n)
#define bins(v,n) binary_search(all(v),n)
#define fr(i,a,b) for(i=a;i<=b;i++)
#define fv(i,a,b) for(i=a;i>=b;i--)
#define f(i,n) for(i=0;i<n;i++)
#define fn(i,n) for(i=n-1;i>=0;i--)
#define pb push_back
#define ppb pop_back
#define all(v) v.begin(),v.end()
#define g(v,n) vl v(n); f(_,n) cin>>v[_]
#define bs(n,x) bitset<n> (x).to_string()
#define invp(v,n) vp v;f(_,n) cin>>v[_].first>>v[_].second
#define seev(v) for(auto ggg:v) cout<<ggg<<"-"
#define print(v) for(auto ggg:v) cout<<ggg<<" "
const ll inf=4e10;
const ll mod=1000000007;
const ll mod2=998244353;
ll power(ll a,ll b,ll p=inf)
{
ll res=1;a%=p;
while(b>0)
{
if(b%2==1)
res=(res*a)%p;
a=(a*a)%p;
b=b/2;
}
return res;
}
ll log(ll n,ll k)
{
ll a=k,b=0;
while(a<=n)
a*=k,b++;
return b;
}
ll todec(ll n,string s)
{
ll i,k=0;
f(i,n)
if(s[i]=='1')
k+=1LL<<(n-i-1);
return k;
}
bool vps(const pair<ll,ll> &a,const pair<ll,ll> &b)
{
return (a.second<b.second);
}
bool fts(const pair<ll,ll> &a,const pair<ll,ll> &b)
{
if(a.first!=b.first)
return (a.first<b.first);
return (a.second>b.second);
}
void solve(ll tc)
{
ll n,m,k=0,j=0,i=0,x=0,y=0,z=0,p=0,q=0,l=0,sum=0,temp=1,flag=0,a=0,b=0,c=0,d=1,r=0,mn=inf,mx=-inf,_,__,mid;
string s1,s2,s3,s;char ch;
cin>>k>>n>>m>>q;
p=n/k+1;
vector<vvvl> v(16,vvvl(p,vvl(k,vl(k,inf))));
f(i,m)
{
cin>>x>>y>>d;
v[0][x/k][x%k][y%k]=d;
}
fr(j,1,15)
f(i,p)
if(i+(1ll<<(j-1))<p)
f(a,k)
f(b,k)
f(c,k)
v[j][i][a][c]=min(v[j][i][a][c],v[j-1][i][a][b]+v[j-1][i+(1ll<<(j-1))][b][c]);
while(q--)
{
cin>>x>>y;
d=y/k-x/k;
i=x/k;
vvl ans(k,vl(k,inf));
f(a,k)
ans[a][x%k]=0;
fn(j,16)
{
if((1ll<<j)<=d)
{
vvl tp(k,vl(k,inf));
f(a,k)
{
f(b,k)
{
f(c,k)
{
tp[a][c]=min(tp[a][c],ans[a][b]+v[j][i][b][c]);
}
}
}
ans=tp;
d-=1ll<<j;
i+=1ll<<j;
}
}
if(ans[x%k][y%k]>=inf)
cout<<-1<<endl;
else
cout<<ans[x%k][y%k]<<endl;
}
}
//Use variables correctly
//Check for boundary conditions
//Write the step statement in while loops
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
ll t=1;
// cin>>t;
while(t--)
{
solve(t);
// cout<<endl;
}
return 0;
}
