#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define xx first
#define yy second
#define pb push_back
using namespace std;
int n, m, k, q;
map<pair<pii, pii>, ll> dp;
ll resi(int a, int b, int x, int y)
{
if (dp[{{a, b}, {x, y}}]) return dp[{{a, b}, {x, y}}];
if ((a+1)==b) return 2000000010;
int mid=a+(b-a)/2;
ll ress=2000000010;
for (int i=0; i<k; i++)
{
ress=min(ress, resi(a, mid, x, i)+resi(mid, b, i, y));
}
dp[{{a, b}, {x, y}}]=ress;
return ress;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
cin>>k>>n>>m>>q;
for (int i=0; i<m; i++)
{
int u, v, t; cin>>u>>v>>t;
dp[{{u/k, v/k}, {u%k, v%k}}]=t;
}
while (q--)
{
int u, v; cin>>u>>v;
int ress=resi(u/k, v/k, u%k, v%k);
if (ress>=2000000010) cout<<-1<<endl;
else cout<<ress<<endl;
}
}
