#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pii pair <int , int>
#define arr3 array <int , 3>
using namespace std;
const int INF = 1e13;
const int maxn = 5e4 + 7;
int k , n , m , o , dp[maxn][7][20];
void solve()
{
cin >> k >> n >> m >> o;
for(int i = 0; i < maxn; i++)
{
for(int j = 0; j < 7; j++)
{
for(int z = 0; z < 20; z++) dp[i][j][z] = INF;
}
}
for(int i = 1; i <= m; i++)
{
int u , v , w;
cin >> u >> v >> w;
dp[u][v%k][0] = min(dp[u][v%k][0] , w);
}
for(int i = 0; i < n; i++)
{
for(int x = 0; x < k; x++)
{
for(int y = 0; y < k; y++)
{
for(int j = 1; j < 20; j++)
{
int mid = ((1 << (j-1)) + i/k)*k + x;
int ed = ((1 << j) + i/k)*k + y;
if(ed >= n) break;
dp[i][y][j] = min(dp[i][y][j] , dp[i][x][j-1] + dp[mid][y][j-1]);
}
}
}
}
while(o--)
{
int a , b; cin >> a >> b;
int step = b/k - a/k , cur[k] , lst[k];
fill(cur , cur+k , INF);
fill(lst , lst+k , INF);
int id = (a/k)*k;
cur[a%k] = 0;
for(int i = 0; i < 19; i++)
{
if((step >> i)&1)
{
for(int j = 0; j < k; j++)
{
lst[j] = cur[j];
cur[j] = INF;
}
for(int x = 0; x < k; x++)
{
for(int y = 0; y < k; y++)
{
cur[y] = min(lst[x] + dp[id+x][y][i] , cur[y]);
}
}
id += (1 << i)*k;
}
}
if(cur[b%k] == INF) cout << -1 << '\n';
else cout << cur[b%k] << '\n';
}
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
//freopen("inp.txt", "r" , stdin);
//freopen("out.txt", "w" , stdout);
solve();
return 0;
}
