#include <bits/stdc++.h>
using i64 = long long;
constexpr int N = 5E4 + 5;
constexpr int L = 20;
constexpr int Inf = 1E9 + 5;
int ans[N][L][5][5];
void combine(int c[5][5], int a[5][5], int b[5][5]) {
for(int i = 0; i < 5; i++) {
for(int j = 0; j < 5; j++) {
for(int k = 0; k < 5; k++) {
c[i][j] = std::min(c[i][j], a[i][k] + b[k][j]);
}
}
}
}
void solve() {
std::fill_n(&ans[0][0][0][0], N * L * 5 * 5, Inf);
int k, n, m, o;
std::cin >> k >> n >> m >> o;
for(int i = 1; i <= m; i++) {
int a, b, t;
std::cin >> a >> b >> t;
ans[a / k][0][a % k][b % k] = t;
}
for(int lg = 1; lg < L; lg++) {
for(int i = 0; i + (1 << lg) < (n + k - 1) / k; i++) {
combine(ans[i][lg], ans[i][lg - 1], ans[i + (1 << (lg - 1))][lg - 1]);
}
}
while(o--) {
int a, b;
std::cin >> a >> b;
int res[5][5], cur = a / k;
std::fill_n(&res[0][0], 5 * 5, Inf);
for(int i = 0; i < 5; i++) res[i][i] = 0;
for(int lg = L - 1; lg >= 0; lg--) {
if(cur + (1 << lg) <= b / k) {
int tmp[5][5];
std::fill_n(&tmp[0][0], 5 * 5, Inf);
combine(tmp, res, ans[cur][lg]);
for(int i = 0; i < 5; i++) {
for(int j = 0; j < 5; j++) {
res[i][j] = tmp[i][j];
}
}
cur += (1 << lg);
}
}
std::cout << (res[a % k][b % k] == Inf ? -1 : res[a % k][b % k]) << "\n";
}
return;
}
signed main() {
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL); std::cout.tie(NULL);
int t = 1; //std::cin >> t;
for(int i = 1; i <= t; i++) {
solve();
}
return 0;
}
