#pragma optimize("Bismillahirrahmanirrahim")
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█■█
//█─█─█▄─█▄─█─█─█─█
//ahmet23 orz...
//FatihSultanMehmedHan
//YavuzSultanSelimHan
//AbdulhamidHan
//Sani buyuk Osman Pasa Plevneden cikmam diyor
#define author tolbi
#include <bits/stdc++.h>
using namespace std;
template<typename X, typename Y> istream& operator>>(istream& is, pair<X,Y> &pr){return is>>pr.first>>pr.second;}
#ifdef tolbi
template<typename X, typename Y> ostream& operator<<(ostream& os, pair<X,Y> pr){return os<<"{ "<<pr.first<<", "<<pr.second<<" }";}
#else
template<typename X, typename Y> ostream& operator<<(ostream& os, pair<X,Y> pr){return os<<pr.first<<" "<<pr.second;}
#endif
ostream& operator<<(ostream& os, bool bl){return os<<(int32_t)bl;}
template<typename X> istream& operator>>(istream& is, vector<X> &arr){for (auto &it : arr) is>>it; return is;}
template<typename X, size_t Y> istream& operator>>(istream& is, array<X,Y> &arr){for (auto &it : arr) is>>it; return is;}
template<typename X> ostream& operator<<(ostream& os, vector<X> &arr){for (auto &it : arr) os<<" "<<it;os<<endl;return os;}
template<typename X, size_t Y> ostream& operator<<(ostream& os, array<X,Y> &arr){for (auto &it : arr) os<<" "<<it;os<<endl;return os;}
#define int long long
#define endl '\n'
#define deci(x) int x;cin>>x;
#define decstr(x) string x;cin>>x;
#define cinarr(x) for (auto &it : x) cin>>it;
#define coutarr(x) for(auto &it : x) cout<<it<<" ";cout<<endl;
#define sortarr(x) sort(x.begin(), x.end())
#define sortrarr(x) sort(x.rbegin(), x.rend())
#define rev(x) reverse(x.begin(), x.end())
#define tol(bi) (1LL<<((int)(bi)))
#define ios ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int INF = LONG_LONG_MAX;
const int MOD = 1e9+7;
mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
int32_t main(){
ios;
int T = 1;
if (!T) cin>>T;
int tno = 0;
while (T-(tno++)){
deci(k);deci(n);deci(m);deci(q);
vector<vector<vector<pair<int,int>>>> arr((n+k-1)/k,vector<vector<pair<int,int>>>(k));
for (int i = 0; i < m; ++i)
{
deci(a);deci(b);deci(x);
arr[a/k][a%k].push_back({b%k,x});
}
while (q--){
deci(a);deci(b);
vector<int> crr(k,INF);
crr[a%k]=0;
if (a==b) {
cout<<0<<endl;
continue;
}
if (b/k<=a/k){
cout<<-1<<endl;
continue;
}
for (int i = a/k; i < b/k; i++){
vector<int> newcrr(k,INF);
for (int j = 0; j < k; j++){
if (crr[j]==INF) continue;
for (int z = 0; z < arr[i][j].size(); z++){
newcrr[arr[i][j][z].first]=min(newcrr[arr[i][j][z].first],crr[j]+arr[i][j][z].second);
}
}
swap(crr,newcrr);
}
if (crr[b%k]==INF){
cout<<-1<<endl;
}
else {
cout<<crr[b%k]<<endl;
}
}
}
}
