#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
typedef unsigned int vec __attribute__((vector_size(32), aligned(4)));
const int N = 50'016;
const unsigned int two31 = 1u<<31;
vec toll[N];
unsigned int dis[N];
int n, m, k, o;
#define SMIN(x, y) ((x)=(x)<(y)?(x):(y))
int order(int v, int u)
{
const int k = ::k;
fill(dis+v, dis+u+1, (1u<<31)-1);
dis[v] = 0;
while (v%k) {
SMIN(*(vec *)(dis + v+k-v%k),
(dis[v] + toll[v]) | (toll[v]&two31));
++v;
}
const int vk = v/k; // vulkan
const int uk = u/k; // united kingdom
Loop (i,vk,uk) {
const int ki = i*k;
Loop (x,0,k) {
SMIN(*(vec *)(dis+ki+k),
(dis[ki+x] + toll[ki+x]) | (toll[ki+x]&two31));
}
}
return dis[u] == (1u<<31)-1? -1: dis[u];
}
int main()
{
cin.tie(0) -> sync_with_stdio(false);
fill(toll, toll+N, vec{~0u, ~0u, ~0u, ~0u, ~0u, ~0u, ~0u, ~0u});
cin >> k >> n >> m >> o;
Loop (i,0,m) {
int v, u, w;
cin >> v >> u >> w;
toll[v][u%k] = w;
}
while (o--) {
int v, u;
cin >> v >> u;
cout << order(v, u) << '\n';
};
}
