#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pi pair<int, int>
#define pii pair<int, pair<int, int> >
#define fi first
#define se second
int n,m,q,k;
struct bru{
int d[5][5];
};
vector<pi>v[200005];
struct node{
int s,e,m;
bru val;
node *l, *r;
node(int _s, int _e){
s = _s, e = _e, m = (s + e)/2;
if(s != e){
l = new node(s, m);
r = new node(m+1, e);
for(int i=0;i<k;i++){
for(int j=0;j<k;j++){
val.d[i][j] = 1e18;
for(int x=0;x<k;x++){
int mid = m*k + x;
for(auto [a, b] : v[mid]){
int tmp = a%k;
val.d[i][j] = min(val.d[i][j], l->val.d[i][x] + r->val.d[tmp][j] + b);
}
}
}
}
}
else{
for(int i=0;i<5;i++)for(int j=0;j<5;j++)val.d[i][j] = 1e18;
for(int i=0;i<k;i++)val.d[i][i] = 0;
}
}
bru query(int S, int E){
if(s == S && e == E)return val;
else if(E <= m)return l->query(S, E);
else if(S > m)return r->query(S, E);
else{
bru left = l->query(S, m);
bru right = r->query(m+1, E);
bru ans;
for(int i=0;i<k;i++){
for(int j=0;j<k;j++){
ans.d[i][j] = 1e18;
for(int x=0;x<k;x++){
int mid = m*k + x;
for(auto [a, b] : v[mid]){
int tmp = a%k;
ans.d[i][j] = min(ans.d[i][j], left.d[i][x] + right.d[tmp][j] + b);
}
}
}
}
return ans;
}
}
}*root;
void solve(){
cin >> k >> n >> m >> q;
while(m--){
int a,b,c;cin >> a >> b >> c;
v[a].push_back({b, c});
}
root = new node(0, (n + k - 1)/k);
while(q--){
int l, r;cin >> l >> r;
bru ans = root->query(l/k, r/k);
cout << (ans.d[l%k][r%k] == 1e18 ? -1 : ans.d[l%k][r%k]) << '\n';
}
}
main(){
ios::sync_with_stdio(0);cin.tie(0);
int t = 1;
//cin >> t;
while(t--){
solve();
}
}
