///TRAN THAI BAO :3
#include <iostream>
#include <cstdio>
using namespace std;
#define maxK 7
#define maxN 50007
#define LOGN 20
#define oo 2000000000
int k, n, m, o;
int up[maxN][maxK][LOGN];
void solve()
{
cin >> k >> n >> m >> o;
int u, v, w;
for(int i = 0; i < n; i++)
for(int j = 0; j < k; j++)
for(int l = 0; l < LOGN; l++)
up[i][j][l] = oo;
for(int i = 0; i < m; i++)
{
cin >> u >> v >> w;
up[u][v%k][0] = w;
}
for(int i = 1; i < LOGN; i++)
{
for(int j = 0; j < n; j++)
{
int curBlock = j/k;
for(int nxt1 = 0; nxt1 < k; nxt1++)
{
for(int nxt2 = 0; nxt2 < k; nxt2++)
{
if(up[j][nxt1][i-1] == oo)
continue;
if((curBlock+1)*k + nxt1 >= n)
continue;
if(up[(curBlock+1)*k + nxt1][nxt2][i-1] == oo)
continue;
up[j][nxt2][i] = min(up[j][nxt2][i], up[j][nxt1][i-1] + up[(curBlock+1)*k + nxt1][nxt2][i-1]);
}
}
}
}
while(o--)
{
int ans[maxK];
for(int i = 0; i < k; i++)
ans[i] = oo;
int a, b;
cin >> a >> b;
ans[a%k] = 0;
int jump = b/k - a/k;
int curBlock = a/k;
for(int i = 0; i < LOGN; i++)
{
if(((jump>>i)&1) == 0)
continue;
int nxtAns[maxK];
for(int j = 0; j < k; j++)
nxtAns[j] = oo;
for(int j = 0; j < k; j++)
{
int cur = curBlock*k + j;
if(cur >= n)
continue;
for(int l = 0; l < k; l++)
{
if(ans[j] == oo)
continue;
if(up[cur][l][i] == oo)
continue;
nxtAns[l] = min(nxtAns[l], ans[j] + up[cur][l][i]);
}
}
curBlock += (1<<i);
for(int j = 0; j < k; j++)
ans[j] = nxtAns[j];
}
if(ans[b%k] == oo)
cout << "-1\n";
else cout << ans[b%k] << "\n";
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}
