#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << ' ' <<
#define nl << '\n'
const int MAXN = 1e5, INF = 1e16;
vector<array<int, 2>> g[MAXN];
int n, k, m, o;
struct SegmentTree{
using T = array<array<int, 5>, 5>;
int sz = 1, l, r;
vector<T> a; T ID, NA;
T comb(const T &x, const T &y, int z){
if(x == NA) return y;
if(y == NA) return x;
T res = ID;
for(int i=0; i<k; ++i)
for(int u=0; u<k; ++u)
for(auto &[v, w] : g[(z-1)*k+u])
for(int j=0; j<k; ++j)
res[i][j] = min(res[i][j], x[i][u] + w + y[v%k][j]);
return res;
}
void init(){
int N = (n + k - 1) / k;
while((sz+=sz)<N);
for(int i=0; i<5; ++i)
ID[i] = {INF, INF, INF, INF, INF};
for(int i=0; i<5; ++i)
NA[i] = {-1, -1, -1, -1, -1};
a.assign(2*sz, ID);
build(0, 0, sz);
}
void build(int x, int lx, int rx){
if(rx - lx == 1){
for(int i=0; lx*k+i<n && i<k; ++i) a[x][i][i] = 0;
return;
}
int mx = (lx + rx) / 2;
build(2*x+1, lx, mx);
build(2*x+2, mx, rx);
if(mx >= n) a[x] = a[2*x+1];
else a[x] = comb(a[2*x+1], a[2*x+2], mx);
}
T query(int x, int lx, int rx){
if(r<=lx || rx<=l) return NA;
if(l<=lx && rx<=r) return a[x];
int mx = (lx + rx) / 2;
return comb(query(2*x+1, lx, mx), query(2*x+2, mx, rx), mx);
}
int query(int L, int R){
l = L/k, r = R/k+1;
return query(0, 0, sz)[L%k][R%k];
}
};
signed main(){
cin.tie(0)->sync_with_stdio(0);
cin >> k >> n >> m >> o;
while(m--){
int u, v, w; cin >> u >> v >> w;
g[u].push_back({v, w});
}
SegmentTree st;
st.init();
while(o--){
int l, r; cin >> l >> r;
l = st.query(l, r);
cout << (l == INF ? -1 : l) << '\n';
}
}
