#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
const int INF = 1e9;
template<typename T> inline istream& operator>>(istream &i, vector<T>& v) {
for (int j = 0; j < (int) v.size(); j++) i >> v[j];
return i;
}
template<typename T> inline ostream& operator<<(ostream &o, const vector<T>& v) {
for (int i = 0; i < (int) v.size(); i++) o << v[i] << ' ';
o << '\n';
return o;
}
struct node {
vector<vector<int>> mat;
node* left, *right;
int i, j;
};
vector<vector<int>> combine(const vector<vector<int>>& mat1, const vector<vector<int>>& mat2) {
if ((int) mat1.size() == 0) return mat2;
if ((int) mat2.size() == 0) return mat1;
int V = (int) mat1.size();
vector<vector<int>> newMat(V, vector<int>(V, INF));
for (int k = 0; k < V; k++) {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
newMat[i][j] = min(newMat[i][j], mat1[i][k] + mat2[k][j]);
}
}
}
return move(newMat);
}
int k, n, m, o;
vector<vector<ii>> g;
node *build(int l, int r) {
//cout << l << ' ' << r << '\n';
if (l == r) {
vector<vector<int>> newMat(k, vector<int>(k, INF));
for (int i = l * k; i < (l + 1) * k; i++) {
for (auto& v : g[i]) {
newMat[i % k][v.first % k] = v.second;
}
}
#ifdef DEBUG
cout << l << ' ' << r << ' ' << newMat;
#endif
//cout << newMat;
return new node{newMat, nullptr, nullptr, l, r};
}
int mid = (l + r) / 2;
node *left = build(l, mid);
node *right = build(mid + 1, r);
//cout << left->mat << right->mat;
vector<vector<int>> newMat = combine(left->mat, right->mat);
#ifdef DEBUG
cout << l << ' ' << r << ' ' << newMat;
#endif
return new node{newMat, left, right, l, r};
}
vector<vector<int>> query(node *cur, int i, int j) {
if (cur->i > j || cur->j < i) return vector<vector<int>>(0);
if (cur->i >= i && cur->j <= j) return cur->mat;
return combine(query(cur->left, i, j), query(cur->right, i, j));
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
cin >> k >> n >> m >> o;
//cout << k << n << m << o;
g.resize(n);
for (int i = 0; i < m; i++) {
int a, b, t;
cin >> a >> b >> t;
g[a].emplace_back(b, t);
}
//cout << (n - 1) / k - 1;
node* root = build(0, (n - 1) / k - 1);
while (o--) {
int s, t;
cin >> s >> t;
int sLayer = s / k;
int tLayer = t / k - 1;
if (sLayer > tLayer) {
cout << "-1\n";
continue;
}
vector<vector<int>> mat = query(root, sLayer, tLayer);
//cout << mat;
int ans = mat[s % k][t % k];
if (ans >= INF) ans = -1;
cout << ans << '\n';
}
return 0;
}
