#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
ll gcd(ll a, ll b) {
return b ? gcd(b, a % b) : a;
}
ll pow(ll a, ll b) {
ll ans = 1;
while (b) {
if (b & 1) ans *= a;
b >>= 1;
a *= a;
}
return ans;
}
ll pow(ll a, ll b, ll c) {
ll ans = 1;
while (b) {
if (b & 1) ans = (ans * a) % c;
b >>= 1;
a = (a * a) % c;
}
return ans;
}
void check(bool b) {
if (b)
cout << "Yes\n";
else
cout << "No\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
ll k,n,m,q;
cin>>k>>n>>m>>q;
ll l=log2(n/k+1)+1;
vector<vector<vector<ll>>>anc(n,vector<vector<ll>>(l,vector<ll>(k,1e14)));
while (m--){
ll a,b,t;
cin>>a>>b>>t;
anc[b][0][a%k]=min(anc[b][0][a%k],t);
}
for (int i = 1; i < l; ++i) {
for (int j = 0; j < n; ++j) {
for (int kk = 0; kk < k; ++kk) {
for (int ll = 0; ll < k; ++ll) {
anc[j][i][ll]=min(anc[j][i][ll], anc[j][i - 1][kk] + anc[max(0LL,(j/k-(1<<(i-1)))*k+kk)][i - 1][ll]);
}
}
}
}
while (q--){
ll a,b;
cin>>a>>b;
if (a/k==b/k){
cout<<-1<<'\n';
continue;
}
ll le=b/k-a/k;
vector<ll>dist(k,1e14);
dist[b%k]=0;
ll cul=b/k;
for (int i = l-1; i >= 0; --i) {
if (le&(1<<i)){
vector<ll>dist2(k,1e14);
for (int j = 0; j < k; ++j) {
for (int ll = 0; ll < k; ++ll) {
if (cul*k+j<n)
dist2[ll]=min(dist2[ll], dist[j] + anc[cul * k + j][i][ll]);
}
}
cul-=1<<i;
swap(dist,dist2);
}
}
if (dist[a%k]==(ll)1e14){
cout<<-1<<'\n';
} else{
cout<<dist[a%k]<<'\n';
}
}
return 0;
}
