#include <bits/stdc++.h>
//#include "debug.h"
//// #pragma GCC optimize("-O3")
//// #pragma GCC optimize("no-stack-protector")
//// #pragma GCC optimize("fast-math")
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
// #pragma GCC target("avx,avx2,fma")
// #pragma GCC optimization ("unroll-loops")
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define f first
#define s second
#define se second
#define vec vector
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
#define sz(x) (int)x.size()
#define pw(x) (1ll<<x)
#define p_b push_back
#define m_p make_pair
#define fast_io ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define sq(x) (x)*(x)
//#define int long long
using namespace std;
//using namespace __gnu_pbds;
typedef pair<long long, long long> PII;
typedef pair<int, int> pii;
typedef long double ld;
typedef long long ll;
typedef pair<long long, long long > pll;
//template <typename T> umax(T &a, T b){return (a<b ? a=b,1 : 0);}
//template <typename T> umin(T &a, T b){return (a>b ? a=b,1 : 0);}
//typedef tree<pii,null_type,less<pii>,rb_tree_tag,tree_order_statistics_node_update> o_set;
const int N=5e4+1;
const int K=5;
const ll inf=1e18;
const ld eps = 1e-9;
const int ppp=73;
const int M=1e9+7;
const ll tx[4]={-1,1,0,0};
const ll ty[4]={0,0,-1,1};
const int lg=21;
const char rev_to[4]={'U','D','L','R'};
auto rnd=bind(uniform_int_distribution<ll>(1,1e9),mt19937(time(0)));
ll up[N][lg][K][K];
void umin(ll &a,ll b){
a=min(a,b);
}
signed main()
{
fast_io;
int k,n,m,q;
cin>>k>>n>>m>>q;
for(int i=0;i<N;i++){
for(int j=0;j<lg;j++){
for(int t=0;t<K;t++){
for(int p=0;p<K;p++)
up[i][j][t][p]=inf;
}
}
}
for(int i=0;i<m;i++){
int a,b,t;
cin>>a>>b>>t;
umin(up[a/k][0][a%k][b%k],t);
}
for(int j=1;j<lg;j++){
for(int i=0;i<N;i++){
for(int t=0;t<k;t++){
if((i+(1<<j))>N)break;
vec<ll>dst(k,inf);
for(int pt=0;pt<k;pt++){
for(int nt=0;nt<k;nt++){
umin(dst[nt],up[i][j-1][t][pt]+up[(i+(1<<(j-1)))][j-1][pt][nt]);
}
}
for(int pt=0;pt<k;pt++)
up[i][j][t][pt]=dst[pt];
}
}
}
while(q--){
int a,b;
cin>>a>>b;
vec<ll>dst(k,inf);
dst[a%k]=0;
int na=a/k,nb=b/k;
for(int j=lg-1;j>=0;j--){
if((na+(1<<j))>nb)continue;
// debug()<<imie(dst);
vec<ll>nd(k,inf);
for(int t=0;t<k;t++){
for(int nt=0;nt<k;nt++){
umin(nd[nt],dst[t]+up[na][j][t][nt]);
}
}
dst=nd;
na+=(1<<j);
// debug()<<imie(dst);
}
cout<<(dst[b%k]==inf?-1:dst[b%k])<<"\n";
}
return 0;
}
/*
5 14 5 1
0 5 9
5 12 10
0 7 7
7 12 8
4 7 10
0 12
*/
