#include <bits/stdc++.h>
using namespace std;
int k, l;
int logarytm(int a) {
int w = 0;
while (a > 0) {
w++;
a /= 2;
}
return w+1;
}
vector<int> polacz(int a, vector<int> b) {
vector<int> w (k, -1);
if (a == -1) {
return w;
}
for (int i = 0; i < k; i++) {
if (b[i] != -1) {
w[i] = b[i]+a;
}
}
return w;
}
vector<int> mini(vector<int> a, vector<int> b) {
vector<int> w (k, 0);
for (int i = 0; i < k; i++) {
if (a[i]==-1 || b[i]==-1) {
w[i] = max(a[i], b[i]);
}
else {
w[i] = min(a[i], b[i]);
}
}
return w;
}
vector<vector<vector<int>>> jp;
vector<vector<vector<int>>> jp2;
vector<int> pot = {1};
int droga (int a, int b) {
int x = a/k, y = b/k, r = b%k;
int p = l-1;
vector<int> odl (5, -1);
odl[a%k] = 0;
while (p >= 0) {
if (x+pot[p]<=y) {
vector<int> pom (k, -1);
for (int i = 0; i < k; i++) {
pom = mini(pom, polacz(odl[i], jp[p][x*k+i]));
}
odl = pom;
x += pot[p];
}
p--;
}
return odl[r];
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
for (int i = 1; i < 20; i++) {
pot.push_back(pot[i-1]*2);
}
int n, m, o;
cin >> k >> n >> m >> o;
vector<vector<pair<int, int>>> g (n);
l = logarytm((n/k)+1);
jp.resize(l, vector<vector<int>>(n, vector<int>(k, -1)));
jp2.resize(l, vector<vector<int>>(n, vector<int>(k, -1)));
for (int i = 0; i < m; i++) {
int a, b, t;
cin >> a >> b >> t;
g[a].push_back(make_pair(b, t));
jp[0][a][b%k] = t;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < k; j++) {
jp2[0][i][j] = (i/k)*k+k+j;
if (jp2[0][i][j] >= n) {
jp2[0][i][j] = n-1;
}
}
}
for (int i = 1; i < l; i++) {
for (int j = 0; j < n; j++) {
for (int x = 0; x < k; x++) {
jp2[i][j][x] = jp2[i-1][jp2[i-1][j][0]][x];
}
}
}
for (int i = 1; i < l; i++) {
for (int j = 0; j < n; j++) {
for (int x = 0; x < k; x++) {
jp[i][j] = mini(jp[i][j], polacz(jp[i-1][j][x], jp[i-1][jp2[i-1][j][x]]));
}
}
}
for (int i = 0; i < o; i++) {
int a, b;
cin >> a >> b;
cout << droga(a, b) << '\n';
}
}
