#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cmath>
using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))
int const sigma = 5;
int const inf = 1000000000;
struct Matrix {
int dp[sigma][sigma];
Matrix() {
for(int i = 0; i < sigma; i++)
for(int j = 0; j < sigma; j++)
dp[i][j] = inf;
}
Matrix operator * (Matrix a) {
Matrix result;
for(int i = 0; i < sigma; i++)
for(int j = 0; j < sigma; j++)
for(int h = 0; h < sigma; h++)
result.dp[i][j] = std::min(result.dp[i][j], dp[i][h] + a.dp[h][j]);
return result;
}
};
class SegmentTree{
private:
std::vector<Matrix> aint;
public:
SegmentTree(int n) {
aint.resize(1 + 4 * n);
}
void build(int node, int from, int to, std::vector<Matrix> &aux) {
if(from < to) {
int mid = (from + to) / 2;
build(node * 2, from, mid, aux);
build(node * 2 + 1, mid + 1, to, aux);
aint[node] = aint[node * 2] * aint[node * 2 + 1];
} else
aint[node] = aux[from];
}
Matrix query(int node, int from, int to, int x, int y) {
if(from == x && to == y)
return aint[node];
else {
int mid = (from + to) / 2;
if(x <= mid && y <= mid)
return query(node * 2, from, mid, x, y);
else if(mid + 1 <= x && mid + 1 <= y)
return query(node * 2 + 1, mid + 1, to, x, y);
else
return query(node *2 , from, mid, x, mid) * query(node * 2 +1 , mid + 1, to, mid + 1, y);
}
}
};
int main() {
std::ios::sync_with_stdio(0);
std::cin.tie(0);
int k, n, m, q;
std::cin >> k >> n >> m >> q;
std::vector<Matrix> aux(n / k);
for(int i = 1;i <= m; i++) {
int x, y, cost;
std::cin >> x >> y >> cost;
aux[x / k].dp[x % k][y % k] = cost;
}
SegmentTree aint(n);
aint.build(1, 0, n / k - 1, aux);
for(int i = 1;i <= q; i++) {
int x, y;
std::cin >> x >> y;
if(x / k == y / k)
std::cout << -1 << '\n';
else {
Matrix ext = aint.query(1, 0, n / k - 1, x/ k, y / k - 1);
int result = ext.dp[x % k][y % k];
if(result == inf)
std::cout << -1 << '\n';
else
std::cout << result << '\n';
}
}
return 0;
}
