#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int nx=5e4+5, kx=16;
ll dp[nx][kx][5], sz, n, m, q, a, b, t;
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
cin>>sz>>n>>m>>q;
for (int i=0; i<nx; i++) for (int j=0; j<kx; j++) for (int k=0; k<sz; k++) dp[i][j][k]=1e18;
for (int i=0; i<m; i++) cin>>a>>b>>t, dp[a][0][b%sz]=t;
for (int i=1; i<kx; i++) for (int j=0; j<n; j++) for (int k=0; k<sz; k++) for (int l=0; l<sz; l++) dp[j][i][k]=min(dp[j][i][k], dp[j][i-1][l]+dp[min(l+((j/sz)+(1<<(i-1)))*sz, (ll)nx-1)][i-1][k]);
//for (int i=0; i<n; i++) for (int j=0; j<3; j++) for (int k=0; k<sz; k++) cout<<i<<' '<<j<<' '<<k<<' '<<dp[i][j][k]<<'\n';
while (q--)
{
cin>>a>>b;
int c=a/sz, tg=b/sz;
vector<pair<ll, ll>> v;
v.push_back({0, a});
if (c==tg)
{
cout<<-1<<'\n';
continue;
}
for (int i=kx-1; i>=0; i--)
{
if (c+(1<<i)>tg) continue;
if (v.empty())
{
cout<<-1<<'\n';
break;
}
if (c+(1<<i)==tg)
{
ll res=1e18;
for (auto x:v) res=min(res, x.first+dp[x.second][i][b%sz]);
if (res==1e18) cout<<-1<<'\n';
else cout<<res<<'\n';
break;
}
vector<ll> tmp(sz, 1e18);
for (int j=0; j<sz; j++) for (auto x:v) tmp[j]=min(tmp[j], x.first+dp[x.second][i][j]);
v.clear();
for (int j=0; j<sz; j++) if (tmp[j]!=1e18) v.push_back({tmp[j], (c+(1<<i))*sz+j});
c+=(1<<i);
}
}
}
