///breaker
#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define ii pair<int,int>
#define mp make_pair
#define in(x) freopen(x,"r",stdin)
#define out(x) freopen(x,"w",stdout)
#define bit(x,i) ((x>>i)&1)
#define lc (id<<1)
#define rc ((id<<1)^1)
const int maxn=5e4+7;
const int inf=1e9+7;
vector<ii>adj[maxn];
int k,n,m,q;
int dp[maxn][25][5][5];
void mix(int target[5][5],int a[5][5],int b[5][5]){
for(int i=0;i<5;i++){
for(int j=0;j<5;j++){
for(int k=0;k<5;k++){
target[i][j]=min(target[i][j],a[i][k]+b[k][j]);
}
}
}
}
void sol(void){
cin>>k>>n>>m>>q;
memset(dp,inf,sizeof(dp));
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
adj[u].push_back({v,w});
dp[u/k][0][u%k][v%k]=w;
}
for(int i=1;i<=20;i++){
for(int j=0;j+(1<<i)<n;j++){
mix(dp[j][i],dp[j][i-1],dp[j+(1<<(i-1))][i-1]);
}
}
while(q--){
int u,v;
cin>>u>>v;
int ans[5][5];
int tmp[5][5];
for(int i=0;i<5;i++){
for(int j=0;j<5;j++){
if(i==j)ans[i][j]=0;
else ans[i][j]=inf;
}
}
for(int left=u/k,right=v/k,i=20;i>=0;i--)if(left+(1<<i)<=right){
for(int j=0;j<5;j++){
for(int k=0;k<5;k++){
tmp[j][k]=ans[j][k];
ans[j][k]=inf;
}
}
mix(ans,tmp,dp[left][i]);
left+=(1<<i);
}
cout<<(ans[u%k][v%k]==inf?-1:ans[u%k][v%k])<<"\n";
}
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t=1;
while(t--){
sol();
}
// you should actually read the stuff at the bottom
return 0;
}
/* stuff you should look for
* int overflow, array bounds
* special cases (n=1?)
* do smth instead of nothing and stay organized
* WRITE STUFF DOWN
* DON'T GET STUCK ON ONE APPROACH
*/
