#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx,avx2")
//#pragma GCC target("popcnt")
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll MAX=2e5+10,P=1e9+7;
const ll INF=0x3f3f3f3f,oo=0x3f3f3f3f3f3f3f3f;
const ldb eps=1e-6;
const ldb PI=acos(-1.0);
const int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
template<typename T>
using vvector = vector<vector<T>>;
int main() {
speed;
int n,m,k,q;
cin>>k>>n>>m>>q;
vvector<ll> G(n,vector<ll>(k,oo));
for (int i=0;i<m;i++) {
ll a,b,w;
cin>>a>>b>>w;
G[a][b%k]=min(G[a][b%k],w);
}
ll spt[n/k+10][k][k][20];
for (int i=n-1;i>=0;i--) {
int ik=i/k;
int ir=i%k;
for (int j=0;j<k;j++) spt[ik][ir][j][0]=G[i][j];
for (int l=1;l<20;l++) {
for (int j=0;j<k;j++) {
spt[ik][ir][j][l]=oo;
if (ik+(1<<l)<=(n-1)/k) {
for (int mid=0;mid<k;mid++) {
spt[ik][ir][j][l]=min(spt[ik][ir][j][l],spt[ik][ir][mid][l-1]+spt[ik+(1<<(l-1))][mid][j][l-1]);
// cout<<mid<<" "<<spt[ik][ir][mid][l-1]<<" "<<spt[ik+(1<<(l-1))][mid][j][l-1]<<" mid spt\n";
}
// cout<<ik<<" "<<ir<<" "<<j<<" "<<l<<" "<<spt[ik][ir][j][l]<<" ik ir j l spt\n";
}
}
}
}
while (q--) {
int a,b;
cin>>a>>b;
int ia=a/k;
int ra=a%k;
int ib=b/k;
int rb=b%k;
int x=ia;
ll md[k];
for (int i=0;i<k;i++) md[i]=oo;
md[ra]=0;
for (int l=19;l>=0;l--) {
// cout<<l<<" l\n";
if (ib-x>=(1<<l)) {
ll nmd[k];
memset(nmd,0x3f,sizeof(nmd));
for (int i=0;i<k;i++) {
for (int j=0;j<k;j++) {
nmd[j]=min(nmd[j],md[i]+spt[x][i][j][l]);
}
}
x+=(1<<l);
for (int i=0;i< k;i++) md[i]=nmd[i];
// cout<<x<<" x\n";
// for (int i=0;i<k;i++) cout<<md[i]<<" ";
// cout<<"\n";
}
}
cout<<(md[rb]>=oo?-1:md[rb])<<"\n";
}
return 0;
}
/*
3 10 9 1
0 3 1
3 6 2
6 9 3
0 4 2
4 7 1
7 9 4
0 5 4
5 8 3
8 9 2
3 9
*/
