#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#define ms(x, y) memset(x, y, sizeof x)
#define sp ,' ',
#define el ,'\n'
using namespace std;
using ll = long long;
using ld = long double;
using pil = pair<int, ll>;
template<typename... Args>
inline void out(Args... args) {
(cout << ... << args);
}
struct r {
template<typename T>
inline r& operator,(T& x) {
cin >> x;
return *this;
}
} in;
#define in in,
int k, n, m, o, w[16][50000][5];
void solve() {
in k, n, m, o;
ms(w, 0x3f);
while (m--) {
int a, b, t; in a, b, t;
w[0][a][b%k] = t;
}
for (int j = 1; j <= 15; j++) for (int u = 0; u < n; u++) {
for (int v = 0; v < k; v++) for (int mid = 0; mid < k; mid++) {
w[j][u][v] = min(w[j][u][v], w[j-1][u][mid] + w[j-1][u/k*k + k*(1<<(j-1)) + mid][v]);
}
}
while (o--) {
int a, b; in a, b;
int d = b/k - a/k;
vector<ll> dist(k, 1e15), prev(k, 1e15);
dist[a%k] = 0;
a = a/k*k;
for (int j = 0; j <= 15; j++) if ((d>>j) & 1) {
prev.swap(dist);
fill(dist.begin(), dist.end(), 0x3f3f3f3f);
for (int v = 0; v < k; v++) for (int u = 0; u < k; u++) {
dist[v] = min(dist[v], prev[u] + w[j][a + u][v]);
}
a += k*(1<<j);
}
if (dist[b%k] < 0x3f3f3f3f) out(dist[b%k] el);
else out(-1 el);
}
}
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t = 1;
// in(t);
while (t--) solve();
}
