#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define sz(a) (int)((a).size())
#define all(a) (a).begin(), (a).end()
#define lsb(x) (x & (-x))
#define vi vector<int>
#define YES { cout << "Yes" << endl; return; }
#define NO { cout << "No" << endl; return; }
using ll = long long;
using pii = std::pair<int, int>;
const int NMAX = 5e4;
const int INF = 1e16;
using namespace std;
int k, n, m, q;
struct Node {
int mat[7][7];
static Node empty() {
Node res;
fill(&res.mat[0][0], &res.mat[0][0] + 7 * 7, INF);
return res;
}
static Node id() {
Node res;
fill(&res.mat[0][0], &res.mat[0][0] + 7 * 7, INF);
for (int i = 0; i < k; ++i) res.mat[i][i] = 0;
return res;
}
static Node merge(const Node& left, const Node& right) {
Node res = Node::empty();
for (int i = 0; i < k; ++i) {
for (int j = 0; j < k; ++j) {
for (int d = 0; d < k; ++d)
res.mat[i][d] = min(res.mat[i][d], left.mat[i][j] + right.mat[j][d]);
}
}
return res;
}
};
Node f[NMAX + 5];
struct Seg {
Node aint[4 * NMAX + 5];
void build(int nod = 1, int st = 0, int dr = n / k - 1) {
if (st == dr) {
aint[nod] = f[st];
return;
}
int m = (st + dr) >> 1;
build(2 * nod, st, m);
build(2 * nod + 1, m + 1, dr);
aint[nod] = Node::merge(aint[2 * nod], aint[2 * nod + 1]);
}
Node query(int l, int r, int nod = 1, int st = 0, int dr = n / k - 1) {
if (st > r || dr < l) return Node::id();
if (l <= st && dr <= r) return aint[nod];
int m = (st + dr) >> 1;
return Node::merge(query(l, r, 2 * nod, st, m), query(l, r, 2 * nod + 1, m + 1, dr));
}
}aint;
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
cin >> k >> n >> m >> q;
for (int i = 0; i < n / k; ++i)
f[i] = Node::empty();
for (int i = 0, a, b, t; i < m; ++i) {
cin >> a >> b >> t;
f[a / k].mat[a % k][b % k] = t;
}
aint.build();
for (int i = 0, u, v; i < q; ++i) {
cin >> u >> v;
if ((u / k) >= (v / k)) {
cout << "-1\n";
continue;
}
auto ret = aint.query(u / k, v / k - 1);
cout << (ret.mat[u % k][v % k] >= INF ? -1 : ret.mat[u % k][v % k]) << '\n';
}
return 0;
}
