#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 7;
struct matrix {
vector<vector<int>> data;
matrix() {}
matrix(int n, int m) : data(n, vector<int>(m)) {}
matrix(vector<vector<int>>& v) : data(v) {}
int row() const {return data.size();}
int col() const {return data[0].size();}
auto & operator [] (int i) {return data[i];}
const auto & operator [] (int i) const {return data[i];}
friend matrix operator * (const matrix& a, const matrix& b) {
matrix res(a.row(), b.col());
for (int i = 0; i < a.row(); ++i)
for (int j = 0; j < b.col(); ++j) {
res[i][j] = inf;
for (int k = 0; k < b.row(); ++k)
res[i][j] = min(res[i][j], a[i][k] + b[k][j]);
}
return res;
}
friend ostream& operator << (ostream& out, const matrix& o) {
for (auto r : o.data) {
for (int i : r) out << i << ' ';
out << '\n';
}
out << '\n';
return out;
}
};
vector<pair<int, int>> radj[50008];
matrix trans[50008][16];
void build_binlift(int n) {
for (int lg = 1; (1 << lg) <= n; ++lg) for (int i = 0; i + (1 << lg) - 1 < n; ++i)
trans[i][lg] = trans[i][lg - 1] * trans[i + (1 << (lg - 1))][lg - 1];
}
matrix identity_matrix(int n) {
matrix I(n, n);
for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) I[i][j] = (i == j ? 0 : inf);
return I;
}
int k;
matrix res; int pt, dist;
matrix query(int l, int r) {
res = identity_matrix(k); pt = l; dist = r - l + 1;
for (int bit = 0; bit < 16; ++bit) if (dist & (1 << bit)) {
res = res * trans[pt][bit];
pt += (1 << bit);
}
return res;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n, m, q, u, v, w; cin >> k >> n >> m >> q;
if (n % k) n = n - n % k + k;
while (m--) cin >> u >> v >> w, radj[v].push_back({u, w});
for (int b = 0; b < n / k; ++b) {
trans[b][0] = matrix(k, k);
for (int i = 0; i < k; ++i) {
for (int j = 0; j < k; ++j) trans[b][0][j][i] = inf;
for (pair<int, int> r_edge : radj[b * k + i]) trans[b][0][r_edge.first % k][i] = r_edge.second;
}
}
build_binlift(n / k); matrix T, dp;
while (q--) {
cin >> u >> v;
if (u == v) cout << 0 << '\n';
else if (u / k + 1 > v / k) cout << -1 << '\n';
else {
T = query(u / k + 1, v / k);
dp = matrix(1, k);
for (int i = u - u % k; i < u - u % k + k; ++i) dp[0][i % k] = (i == u ? 0 : inf);
dp = dp * T;
cout << (dp[0][v % k] == inf ? -1 : dp[0][v % k]) << '\n';
}
}
}
