#include<iostream>
using namespace std;
typedef long long ll;
const int N = 50001, C = 6, K = 17;
const ll inf = 1e18;
ll G[N][C];
ll dis[N][C][K];
int main()
{
int k, n, m, o;
cin >> k >> n >> m >> o;
for(int i = 0; i < n; i++)
for(int j = 0; j < k; j++)
G[i][j] = inf;
for(int i = 0; i < n; i ++)
for(int j = 0; j < k; j++)
for(int l = 0; l < K; l++)
dis[i][j][k] = inf;
for(int i = 0; i < m; i++)
{
ll a, b, t;
cin >> a >> b >> t;
G[a][b % k] = min(G[a][b % k], t);
}
for(int i = n - 1; i >= 0; i--)
{
for(int j = 0; j < k; j++)
dis[i][j][0] = G[i][j];
for(int p = 1; p < K; p++)
for(int j = 0; j < k && (1 << p) * k + i - i%k + j < n; j++)
{
ll mx = inf;
for(int l = 0; l < k; l++)
{
int v = (1 << (p-1)) * k + i - i%k + l;
if(v >= n) break;
mx = min(mx, dis[i][l][p - 1] + dis[v][j][p-1]);
}
dis[i][j][p] = mx;
}
}
while(o--)
{
int a, b;
cin >> a >> b;
int d = (b / k) - (a / k);
if(d == 0)
{
cout << -1 << '\n';
continue;
}
ll dist[k], v[k];
int f = __builtin_ctz(d);
for(int i = 0; i < k; i++)
{
dist[i] = dis[a][i][f];
v[i] = (a - a % k) + (1 << f) * k + i;
}
for(int l = f + 1; l < K; l++)
if((1 << l) & d)
{
ll newD[k];
for(int i = 0; i < k; i++)
newD[i] = inf;
for(int i = 0; i < k; i++)
for(int j = 0; j < k; j++)
newD[j] = min(dist[i] + dis[v[i]][j][l], newD[j]);
for(int i = 0; i < k; i++)
dist[i] = newD[i], v[i] += (1 << l) * k;
}
cout << (dist[b % k] >= inf ? -1 : dist[b%k]) << '\n';
}
return 0;
}
