#include <iostream>
#include <vector>
using namespace std;
#define ll long long
#define INF (ll) 1000000000000000
int main(void){
// freopen("input.txt", "r", stdin);
ll K, n, m, q;
cin>>K>>n>>m>>q;
vector<vector<vector<pair<ll, ll>>>> lift;
lift.assign(n, {});
for(ll i = 0; i<n; i++) lift[i].assign(20, vector<pair<ll, ll>>(K, {-1, INF}));
for(ll i = 0; i<m; i++){
ll a, b, t; cin>>a>>b>>t;
lift[a][0][b%K] = {b, t};
}
for(ll i = 1; i<20; i++){
for(ll j = 0; j<n; j++){
for(ll indR = 0; indR<K; indR++){
ll mn = INF;
ll works = -1;
for(ll x = 0; x<K; x++){
if(lift[j][i-1][x].first == -1 || lift[j][i-1][x].second>=INF)continue;
if(lift[j][i-1][x].second + lift[lift[j][i-1][x].first][i-1][indR].second >= INF) continue;
mn = min(mn, lift[j][i-1][x].second + lift[lift[j][i-1][x].first][i-1][indR].second);
works = lift[lift[j][i-1][x].first][i-1][indR].first;
}
if(works!=-1) lift[j][i][indR] = {works, mn};
else lift[j][i][indR] = {-1, INF};
}
}
}
for(ll i = 0; i<q; i++){
ll a, b; cin>>a>>b;
vector<pair<ll, ll>> s (K, {-1, INF});
s[a%K] = {a, 0};
if(a == b){cout<<0<<endl; continue;}
ll diff = (b/K) - (a/K);
if(diff<0){cout<<-1<<endl; continue;};
ll currLvl = a/K;
for(ll j = 19; j>=0; j--){
if((1<<j) & diff){
vector<pair<ll, ll>> newS (K, {-1, INF});
for(ll indR = 0; indR<K; indR++){
ll mn = INF;
ll works = -1;
for(ll x = 0; x<K; x++){
if(s[x].first == -1 || s[x].second + lift[s[x].first][j][indR].second>=INF) continue;
mn = min(mn, s[x].second + lift[s[x].first][j][indR].second);
works = x;
}
if(works != -1)
newS[indR] = {lift[s[works].first][j][indR].first, mn};
else newS[indR] = {-1, INF};
}
s = newS;
}
}
if(s[b%K].first == -1 || s[b%K].second >= INF){cout<<-1<<endl; continue;}
else cout<<s[b%K].second<<endl;
}
return 0;
}
