#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long double ld;
typedef pair<ll, ll> pll;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define ms memset
#define pb push_back
#define F first
#define S second
ll MOD = 1000000007;
ll INF = 1000000000;
ll power(ll base, ll n){
if (n == 0) return 1;
if (n == 1) return base;
ll halfn = power(base, n/2);
if (n % 2 == 0) return (halfn * halfn) % MOD;
return (((halfn * halfn) % MOD) * base) % MOD;
}
ll inverse(ll n){
return power(n, MOD-2);
}
ll add(ll a, ll b){
return (a+b) % MOD;
}
ll mul(ll a, ll b){
return (a*b) % MOD;
}
ll gcd(ll a, ll b){
if (a == 0) return b;
if (a == 1) return 1;
return gcd(b%a, a);
}
int k;
struct piece{
int dist[5][5];
void init(){
ms(dist, -1, sizeof(dist));
}
void upd(int a, int b, int val){
if (dist[a][b] == -1) dist[a][b] = val;
else dist[a][b] = min(dist[a][b], val);
}
};
piece comb(piece p1, piece p2){
piece ans; ans.init();
FOR(i, 0, k){
FOR(j, 0, k){
FOR(l, 0, k){
if (p1.dist[i][l] == -1 || p2.dist[l][j] == -1) continue;
ans.upd(i, j, p1.dist[i][l] + p2.dist[l][j]);
}
}
}
return ans;
}
int main(){
ios::sync_with_stdio(false);
int n, m, o; cin >> k >> n >> m >> o;
int B = (n-1)/k+1;
piece g[B][19];
FOR(i, 0, B){
FOR(j, 0, 19) g[i][j].init();
}
FOR(i, 0, m){
int a, b, t; cin >> a >> b >> t;
g[a/k][0].upd(a%k, b%k, t);
}
FOR(i, 1, 19){
FOR(j, 0, B-(1<<i)){
g[j][i] = comb(g[j][i-1], g[j+(1<<(i-1))][i-1]);
}
}
while (o--){
int a, b; cin >> a >> b;
piece ans; ans.init();
int found = -1;
int len = b/k - a/k;
int cnt = 0; int pos = a/k;
while (len > 0){
if (len % 2 == 1){
if (found == -1){
ans = g[pos][cnt]; found = 1;
}
else ans = comb(ans, g[pos][cnt]);
pos += (1<<cnt);
}
len /= 2;
cnt++;
}
cout << ans.dist[a%k][b%k] << '\n';
}
}
