#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int k, n, m, o; cin >> k >> n >> m >> o;
vector<vector<vector<int>>> dist(n, vector<vector<int>>(16, vector<int>(k, 1e9)));
for (int i = 0; i < m; ++i) {
int a, b, t; cin >> a >> b >> t;
dist[a][0][b % k] = t;
}
for (int i = 1; i < 16; ++i) {
for (int a = 0; a < n; ++a) {
for (int b = 0; b < k; ++b) {
for (int c = 0; c < k; ++c) {
if ((a / k + (1 << (i - 1))) * k + b < n)
dist[a][i][c] = min(dist[a][i][c], dist[a][i - 1][b] + dist[(a / k + (1 << (i - 1))) * k + b][i - 1][c]);
}
}
}
}
while (o--) {
int a, b; cin >> a >> b;
int d = b / k - a / k;
vector<int> places(k, 1e9);
places[a % k] = 0;
int st = a / k * k;
for (int i = 0; i < 16; ++i) {
if (d & (1 << i)) {
vector<int> nplaces(k, 1e9);
for (int fr = 0; fr < k; ++fr) {
for (int j = 0; j < k; ++j) {
nplaces[j] = min(nplaces[j], places[st + fr] + dist[st + fr][i][j]);
}
}
st += (1 << i) * k;
places = nplaces;
}
}
cout << (places[b % k] == 1e9 ? -1 : places[b % k]) << '\n';
}
return 0;
}
