#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<pair<int, int>> places = {{a, 0}};
for (int i = 0; i < 16; ++i) {
if (d & (1 << i)) {
vector<pair<int, int>> nplaces;
for (pair<int, int> fr : places) {
for (int j = 0; j < k; ++j) {
nplaces.push_back({(fr.first / k + (1 << i)) * k + j, min(fr.second + dist[fr.first][i][j], (int) 1e9)});
}
}
places = nplaces;
}
}
int ans = 1e9;
for (pair<int, int> i : places) {
if (i.first == b) {
ans = i.second;
}
}
cout << (ans == 1e9 ? -1 : ans) << '\n';
}
return 0;
}
