#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
#define ll long long
#define F first
#define S second
#define pb push_back
#define lc (ind << 1)
#define rc (lc | 1)
#define md ((b + e) >> 1)
const ll N = 5e4 + 5;
const ll M = 5 + 3;
const ll LOG = 17;
const ll INF = 1e18 + 5;
const ll ziad = 1e9 + 5;
const ll MOD = 1e9 + 7;
int k, n, m, q;
ll dis[N][LOG][M];
ll dist[2][M];
inline void build(){
int ghar = (n - 1) / k;
for (int i = 1; i < LOG; i ++){
for (int A = 0; A < n; A ++){
int X = A / k;
int Y = X + (1 << (i - 1));
int Z = Y + (1 << (i - 1));
if (ghar < Z) break;
for (int j = 0; j < k; j ++){
int B = Y * k + j;
if (n <= B) break;
for (int l = 0; l < k; l ++){
int C = Z * k + l;
if (n <= C) break;
dis[A][i][l] = min(dis[A][i][l], dis[A][i - 1][j] + dis[B][i - 1][l]);
}
}
}
}
return;
}
inline ll get(int s, int e){
if (e / k <= s / k) return -1;
memset(dist, 63, sizeof dist);
dist[0][s % k] = 0;
ll state = s / k;
ll dif = e / k - s / k;
for (int i = LOG - 1; i >= 0; i --){
if ((dif >> i) & 1){
for (int a = 0; a < k; a ++){
int A = state * k + a;
if (n <= A) break;
for (int b = 0; b < k; b ++){
int B = (state + (1 << i)) * k + b;
if (n <= B) break;
dist[1][b] = min(dist[1][b], dist[0][a] + dis[A][i][b]);
}
}
for (int j = 0; j < k; j ++){
dist[0][j] = dist[1][j];
dist[1][j] = INF;
}
state += (1 << i);
}
}
if (ziad < dist[0][e % k]) return -1;
return dist[0][e % k];
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
memset(dis, 63, sizeof dis);
cin >> k >> n >> m >> q;
for (int i = 0; i < m; i ++){
int u, v, w;
cin >> u >> v >> w;
dis[u][0][v % k] = w;
}
build();
while (q --){
int s, e;
cin >> s >> e;
cout << get(s, e) << '\n';
}
return 0;
}
