// In the name of God
// Hope is last to die
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define pb push_back
#define int long long
#define S second
#define F first
#define mp make_pair
#define smax(x, y) (x) = max((x), (y))
#define smin(x, y) (x) = min((x), (y))
#define all(x) (x).begin(), (x).end()
#define len(x) ((int)(x).size())
const int maxn = 4e5, lg = 17;
const int inf = 1e9 + 7, mod = 1e9 + 7;
int k, n, m, q;
struct D{
int node[5];
D(){
for(int i = 0; i < 5; i++) node[i] = inf;
}
} dp[maxn][lg];
D merge(D a, int u, int b){
int aa[5];
for(int i = 0; i < k; i++){
int x = inf;
for(int j = 0; j < k; j++) smin(x, a.node[j] + dp[u * k + j][b].node[i]);
aa[i] = x;
}
for(int i = 0; i < k; i++) a.node[i] = aa[i];
return a;
}
int32_t main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> k >> n >> m >> q;
for(int i = 0; i < m; i++){
int u, v, w; cin >> u >> v >> w;
dp[u][0].node[v % k] = w;
}
for(int i = n - 1; i >= 0; i--){
for(int j = 1; j < lg; j++){
dp[i][j] = merge(dp[i][j - 1], (i / k) + (1ll << (j - 1)), j - 1);
}
}
while(q--){
int u, v; cin >> u >> v;
if(u / k >= v / k){
cout << -1 << '\n';
continue;
}
int x = u / k + 1, y = v / k;
D ans = dp[u][0];
for(int i = 0; i < lg; i++){
if((y - x) & (1ll << i)){
ans = merge(ans, x, i);
x += 1ll << i;
}
}
if(ans.node[v % k] >= inf) cout << -1 << '\n';
else cout << ans.node[v % k] << '\n';
}
return 0;
}
