//package ojuz;
import java.io.*;
import java.util.*;
public class toll {
public static final int inf = 1_000_000_000;
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
String[] first = reader.readLine().split(" ");
int k = Integer.parseInt(first[0]), n = Math.floorDiv(Integer.parseInt(first[1]) + k - 1, k) * k, m = Integer.parseInt(first[2]), q = Integer.parseInt(first[3]);
int log = 32 - Integer.numberOfLeadingZeros(n - 1);
// for node i, the min cost of toll up to (2 ** i) layers after, ending on node k on that layer
int[][][] lift = new int[log][n][k];
for (int[][] arr : lift) for (int[] ar : arr) Arrays.fill(ar, inf);
for (int i = 0; i < m; i++) {
String[] edge = reader.readLine().split(" ");
int a = Integer.parseInt(edge[0]), b = Integer.parseInt(edge[1]), t = Integer.parseInt(edge[2]);
lift[0][a][b % k] = t;
}
for (int i = 1; i < log; i++) {
for (int j = 0; j < n; j++) {
int next = (j / k) * k + (k << (i - 1));
if (next >= n) continue;
for (int l = 0; l < k; l++) {
for (int o = 0; o < k; o++) {
lift[i][j][l] = Math.min(lift[i][j][l], lift[i - 1][j][o] + lift[i - 1][next + o][l]);
}
}
}
}
int[] best = new int[k];
int[] aux = new int[k];
for (int i = 0; i < q; i++) {
String[] query = reader.readLine().split(" ");
int a = Integer.parseInt(query[0]), b = Integer.parseInt(query[1]);
int dist = (b / k) - (a / k);
int cur = a / k;
Arrays.fill(best, inf);
best[a % k] = 0;
for (int j = log; j >= 0; j--) {
if (dist >= (1 << j)) {
dist -= 1 << j;
Arrays.fill(aux, inf);
for (int l = 0; l < k; l++) {
for (int o = 0; o < k; o++) {
aux[l] = Math.min(aux[l], best[o] + lift[j][cur * k + o][l]);
}
}
cur += 1 << j;
int[] temp = best;
best = aux;
aux = temp;
}
}
writer.write(best[b % k] == inf ? "-1" : String.valueOf(best[b % k]));
writer.newLine();
}
writer.flush();
}
}
