#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvl = vector<vll>;
using pll = pair<ll,ll>;
using vpl = vector<pll>;
using vvp = vector<vpl>;
#define f fisrt
#define s second
#define pb push_back
#define all(v) v.begin(),v.end()
int main(){
ios_base::sync_with_stdio(0);cin.tie(NULL);
ll k, n, m, o, f=20, a, b, t;
cin >> k >> n >> m >> o;
n+=k-n%k;
vector<vvl> ed(f, vvl(n, vll(k, 1e11)));
for(ll i = 0; i < m; ++i){
cin >> a >> b >> t;
ed[0][a][b%k]=t;
}
for(ll h = 1; h < f; ++h){
for(ll i = 0; i < n; ++i){
for(ll j = 0; j < k; ++j){
for(ll p = 0; p < k; ++p){
ll l = i-i%k+(1<<(h-1))*k+p;
if(l<n)ed[h][i][j] = min(ed[h][i][j], ed[h-1][i][p] + ed[h-1][l][j]);
}
}
}
}
while(o--){
vll dis(k, 1e11), dis2;
cin >> a >> b;
t = b/k-a/k;
dis[a%k]=0;
a-=a%k;
for(ll h = f-1; h >= 0; --h){
if((1<<h)<=t){
dis2 = vll(k, 1e11);
for(ll i = 0; i < k; ++i){
for(ll j = 0; j < k; ++j){
dis2[i] = min(dis2[i],dis[j]+ed[h][a+j][i]);
}
}
t-=(1<<h);
a+=(1<<h)*k;
swap(dis, dis2);
}
}
if(dis[b%k]<1e11)cout << dis[b%k] << "\n";
else cout << "-1\n";
}
}
