#include "bits/stdc++.h"
using namespace std;
// For Ordered Set
/*
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
// For snippet use pbds
*/
#define pi 3.141592653589793238
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define ll long long
#define int long long
ll M = 1000000007;
// Solution Starts Here.....
const int NN = 5e4+5;
const int KK = 7;
const int Log = 20;
int dp[NN][KK][Log];
void solve(){
int K, n, m, O;
cin >> K >> n >> m >> O;
vector<int> adj[n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < K; j++) {
for (int k = 0; k < Log; k++) {
dp[i][j][k] = 1e14;
}
}
}
for (int i = 0; i < m; i++) {
int a, b, t; cin >> a >> b >> t;
dp[a][b%K][0] = t;
}
for (int j = 1; j < Log; j++) {
for (int i = 0; i < n; i++) {
for (int k = 0; k < K; k++) {
int nxt = i/K + (1<<j) + k;
if(nxt>=n) continue;
// update dp[i][j][k]
nxt = i/K + (1<<(j-1));
for (int k1 = 0; k1 <K; k1++) {
int val1 = dp[i][k1][j-1];
int val2 = dp[K*nxt+k1][k][j-1];
if(val1 < 1e14 and val2 < 1e14) dp[i][k][j] = min(dp[i][k][j],val1 + val2);
}
}
}
}
vector<int> id;
map<pair<int,int>, int> mp;
function<int(int,int, int)> query = [&](int a, int b, int ind){
if(a == b) return 0ll;
int val = 1e14;
if(a/K >= b/K) return val;
if(mp.find({a, b}) != mp.end()) return mp[{a, b}];
int ans = 1e14;
int i = id[ind];
for (int j = 0; j < K; j++) {
// dbg(dp[a][j][i], j);
int Lval;
int t_a = (a/K + (1<<i))*K + j;
if(mp.find({t_a, b}) != mp.end()) Lval = mp[{t_a, b}];
else Lval = query(t_a, b, ind+1);
if(Lval < 1e14) ans = min(ans, dp[a][j][i] + Lval);
//dbg(ans);
}
return mp[{a, b}] = ans;
};
// O = 1;
while(O--){
int a, b; cin >> a >> b;
//dbg(a, b);
int dist = b/K - a/K;
id.clear();
for (int i = 0; i < Log; i++) {
if(dist & (1<<i)) id.push_back(i);
}
int ans = query(a, b, 0);
if(ans >= 1e14){
cout << "-1\n";
}
else cout << ans << "\n";
}
}
int32_t main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int TET = 1;
// cin >> TET;
for (int i = 1; i <= TET; i++)
{
solve();
}
}
