#include <bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x3F3F3F3F3F3F3F
const int MXN = 5e4 + 5;
struct DATA
{
int a[5][5];
};
int K;
DATA st[MXN << 2];
DATA arr[MXN];
DATA combine(DATA x, DATA y, DATA z)
{
if (y.a[0][0] == -1) return x;
if (x.a[0][0] == -1) return y;
DATA res;
for (int i = 0; i < K; i++) for (int j = 0; j < K; j++) res.a[i][j] = inf;
for (int L = 0; L < K; L++)
{
for (int i = 0; i < K; i++)
{
for (int j = 0; j < K; j++)
{
for (int R = 0; R < K; R++)
{
res.a[L][R] = min(res.a[L][R], x.a[L][i] + z.a[i][j] + y.a[j][R]);
}
}
}
}
return res;
}
void build(int l, int r, int x)
{
if (l == r)
{
for (int i = 0; i < K; i++) for (int j = 0; j < K; j++) st[x].a[i][j] = (i == j ? 0 : inf);
return;
}
int mid = (l + r) >> 1;
build(l, mid, 2*x);
build(mid + 1, r, 2*x + 1);
st[x] = combine(st[2*x], st[2*x + 1], arr[mid]);
}
DATA get(int l, int r, int x, int lx, int rx)
{
if (l > rx || r < lx)
{
DATA x;
x.a[0][0] = -1;
return x;
}
if (l >= lx && r <= rx) return st[x];
int mid = (l + r) >> 1;
return combine(get(l, mid, 2*x, lx, rx), get(mid + 1, r, 2*x + 1, lx, rx), arr[mid]);
}
void _()
{
int n, m, q;
cin >> K >> n >> m >> q;
while (n % K) n++;
for (int i = 0; i < n / K; i++) for (int j = 0; j < K; j++) for (int k = 0; k < K; k++) arr[i].a[j][k] = inf;
while (m--)
{
int a, b, t;
cin >> a >> b >> t;
arr[a / K].a[a % K][b % K] = min(arr[a / K].a[a % K][b % K], t);
}
build(0, n / K - 1, 1);
while (q--)
{
int a, b;
cin >> a >> b;
DATA x = get(0, n / K - 1, 1, a / K, b / K);
cout << (x.a[a % K][b % K] >= inf ? -1 : x.a[a % K][b % K]) << '\n';
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// cin >> t;
while (t--) _();
}
