#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const ll MAXN = 5e4 + 10;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
struct querie
{
ll ql, qr, index;
querie(){};
querie(ll _ql, ll _qr, ll _index)
{
ql = _ql;
qr = _qr;
index = _index;
}
};
ll k, n, m, q;
vector < pair < ll, ll > > g[MAXN];
void read()
{
cin >> k >> n >> m >> q;
ll from, to, cost;
for (ll i = 1; i <= m; ++ i)
{
cin >> from >> to >> cost;
g[from].push_back(make_pair(to, cost));
}
}
void queries()
{
ll ql, qr;
for (ll i = 1; i <= q; ++ i)
{
cin >> ql >> qr;
int st_bucket = ql/k, fi_bucket = qr/k;
vector < ll > ans(k, 1e17);
ans[ql % k] = 0;
for (int i = st_bucket+1; i <= fi_bucket; ++ i) /// go throught the buckets
{
vector < ll > curr(k, 1e17);
for (int st = 0; st < k; ++ st) ///
{
for (auto &[nb, cost]: g[(i-1) * k + st])
{
curr[nb%k] = min(curr[nb%k], cost + ans[st]);
}
}
ans = curr;
}
if(ans[qr%k] == 1e17)cout << -1 << endl;
else cout << ans[qr%k] << endl;
}
}
int main()
{
speed();
read();
queries();
return 0;
}
