#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e15 + 7;
#ifndef LOCAL
#define cerr if(false) cerr
#endif
typedef vector<vector<ll> > mat;
const ll MAX_N = 1e5 + 10;
ll n, m, k, q;
mat mult(const mat &a, const mat &b) {
mat ret = mat(k, vector<ll>(k, mod));
if(a.empty()) { return b; }
if(b.empty()) { return a; }
for(ll i = 0; i < k; i ++) {
for(ll j = 0; j < k; j ++) {
for(ll mid = 0; mid < k; mid ++) {
chkmin(ret[i][j], a[i][mid] + b[mid][j]);
}
}
}
return ret;
}
mat prec[MAX_N], jmp[MAX_N];
const ll JMP = 300;
ll loc[MAX_N];
vector<pair<ll, ll> > g[MAX_N];
signed main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> k >> n >> m >> q;
for(ll i = 0; i < m; i ++) {
ll a, b, c;
cin >> a >> b >> c;
g[a].push_back({b, c});
}
for(ll i = 0; i < n; i += k) {
prec[i / k] = mat(k, vector<ll>(k, mod));
for(ll j = i; j < i + k; j ++) {
for(auto it : g[j]) {
chkmin(prec[i / k][j % k][it.first % k], it.second);
}
}
}
fill(loc, loc + MAX_N, mod);
for(ll i = (n + k - 1) / k; i >= 0; i --) {
if(i % JMP == 0) {
jmp[i / k] = prec[i / k];
loc[i / k] = i / k + 1;
} else {
jmp[i / k] = mult(prec[i / k], jmp[i / k + 1]);
loc[i / k] = loc[i / k + 1];
}
}
while(q --) {
ll a, b;
cin >> a >> b;
if(a / k >= b / k) {
cout << -1 << endl;
continue;
}
mat ret = prec[a / k];
a += k;
ll gra = a / k, grb = b / k;
while(gra < grb) {
if(loc[gra] < grb) {
ret = mult(ret, jmp[gra]);
gra = loc[gra];
} else {
ret = mult(ret, prec[gra]);
gra ++;
}
}
if(ret[a % k][b % k] == mod) {
cout << -1 << endl;
} else {
cout << ret[a % k][b % k] << endl;
}
}
return 0;
}
