#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define pb push_back
const ll INF = (ll)4e18;
int K, N, M, Q;
int leafCount; // number of base matrices = max(0, L-1)
int segSize;
vector<vector<ll>> seg; // segment tree nodes: each node stores a KxK matrix in row-major
// identity matrix for min-plus semiring
vector<ll> identity_matrix(){
vector<ll> I(K*K, INF);
for(int i=0;i<K;i++) I[i*K + i] = 0;
return I;
}
// multiply A ⊗ B in min-plus semiring. A,B are KxK row-major.
vector<ll> multiply_mat(const vector<ll>& A, const vector<ll>& B){
vector<ll> C(K*K, INF);
for(int i=0;i<K;i++){
int base_i = i*K;
for(int k=0;k<K;k++){
ll aik = A[base_i + k];
if(aik == INF) continue;
int base_k = k*K;
for(int j=0;j<K;j++){
ll bkj = B[base_k + j];
if(bkj == INF) continue;
ll cand = aik + bkj;
ll &dst = C[base_i + j];
if(cand < dst) dst = cand;
}
}
}
return C;
}
// build segtree from base array of matrices (size = leafCount)
void build_segtree(const vector<vector<ll>>& base){
int need = max(1, leafCount);
segSize = 1;
while(segSize < need) segSize <<= 1;
seg.assign(2*segSize, identity_matrix());
for(int i=0;i<leafCount;i++) seg[segSize + i] = base[i];
for(int i=segSize-1;i>=1;i--){
seg[i] = multiply_mat(seg[2*i], seg[2*i+1]); // left ⊗ right
}
}
// range product [l, r] inclusive over base indices (0..leafCount-1)
vector<ll> range_product(int l, int r){
if(l > r) return identity_matrix();
l += segSize; r += segSize;
vector<ll> leftRes = identity_matrix();
vector<ll> rightRes = identity_matrix();
while(l <= r){
if(l & 1){
leftRes = multiply_mat(leftRes, seg[l++]);
}
if(!(r & 1)){
rightRes = multiply_mat(seg[r--], rightRes);
}
l >>= 1; r >>= 1;
}
return multiply_mat(leftRes, rightRes);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
if(!(cin >> K >> N >> M >> Q)) return 0;
int L = (N + K - 1) / K;
leafCount = max(0, L - 1);
vector<vector<ll>> base(leafCount, vector<ll>(K*K, INF));
for(int i=0;i<M;i++){
int a,b; ll t; cin >> a >> b >> t;
if(a < 0 || a >= N || b < 0 || b >= N) continue;
int la = a / K;
int lb = b / K;
if(lb != la + 1) continue; // only edges to next layer kept
int pa = a % K;
int pb = b % K;
int idx = pa * K + pb;
base[la][idx] = min(base[la][idx], t);
}
build_segtree(base);
for(int qi=0; qi<Q; qi++){
int a,b; cin >> a >> b;
if(a < 0 || a >= N || b < 0 || b >= N){
cout << -1 << '\n';
continue;
}
int sa = a / K, sb = b / K;
int pa = a % K, pb = b % K;
if(sa == sb){
if(a == b) cout << 0 << '\n';
else cout << -1 << '\n';
continue;
}
if(sa > sb){
cout << -1 << '\n';
continue;
}
if(leafCount == 0){
cout << -1 << '\n';
continue;
}
int L_from = sa;
int L_to = sb - 1;
if(L_from < 0) L_from = 0;
if(L_to >= leafCount){ cout << -1 << '\n'; continue; }
vector<ll> P = range_product(L_from, L_to);
ll ans = P[pa * K + pb];
if(ans >= INF/2) cout << -1 << '\n';
else cout << ans << '\n';
}
return 0;
}
