#include <bits/stdc++.h>
#define FIXED_FLOAT(x) std::fixed <<std::setprecision(20) << (x)
#define all(v) (v).begin(), (v).end()
using namespace std;
#define forn(i,n) for (int i = 0; i < (n); ++i)
#define rforn(i, n) for(int i = (n) - 1;i >= 0;--i)
using ll = long long;
int mod = (ll)1e9 + 7;
#define PI acos(-1)
typedef pair<int, int> pairs;
const int INF = 1e9 + 1;
const int N = 5e4 + 100;
const double eps = 1e-7;
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;
template <typename XPAX>
void ckma(XPAX &x, XPAX y) {
x = (x < y ? y : x);
}
template <typename XPAX>
void ckmi(XPAX &x, XPAX y) {
x = (x > y ? y : x);
}
int n, k, m, q;
const int MX = 17;
int F[N][MX][5][5], tmp[5][5], ans[5][5];
void comb(int tar[5][5], int a[5][5], int b[5][5]) {
for(int x = 0;x < k;++x)
for(int y = 0;y < k;++y)
for(int z = 0;z < k;++z)
tar[x][y] = min(tar[x][y], a[x][z] + b[z][y]);
}
void solve() {
cin >> k >> n >> m >> q;
memset(F, 0x3f, sizeof F);
while(m--) {
int a, b, t;
cin >> a >> b >> t;
F[a / k][0][a % k][b % k] = t;
}
for(int j = 1;j < MX;++j) {
for(int i = 0;i + (1 << j) < (n + k - 1) / k;++i) {
comb(F[i][j], F[i][j - 1], F[i + (1 << j - 1)][j - 1]);
}
}
while(q--) {
int a, b;
cin >> a >> b;
memset(ans, 0x3f, sizeof(ans));
forn(i, 5) ans[i][i] = 0;
for(int cur = a / k, T = b / k,i = MX - 1;~i;--i) {
if(cur + (1 << i) <= T) {
memset(tmp, 0x3f, sizeof tmp);
comb(tmp, ans, F[cur][i]);
memcpy(ans, tmp, sizeof ans);
cur += 1 << i;
}
}
cout << (ans[a % k][b % k] == 0x3f3f3f3f ? -1 : ans[a % k][b % k]) << '\n';
}
}
void test_case() {
int t;
cin >> t;
forn(p, t) {
//cout << "Case #" << p + 1 << ": ";
solve();
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
solve();
}
