#include <bits/stdc++.h>
#define NMAX 50000
#define LOG 17
#define ll long long int
#define BASE 1024
#define MOD 1000000009
using namespace std;
ifstream fin("cod.in");
ofstream fout("cod.out");
/// dp[i][p][j] = i -> [i/k] + (1<<p) + j
int dp[NMAX+1][LOG+1][5];
vector<pair<int,int>> adj[NMAX+1];
int k,n,m,q;
int main()
{
cin >> k >> n >> m >> q;
while(m--)
{
int a,b,c;
cin >> a >> b >> c;
adj[a].push_back({b,c});
}
for(int i=0;i<n;i++)
{
for(int p=0;p<=LOG;p++)
{
for(int j=0;j<k;j++)
{
dp[i][p][j] = 1e9;
}
}
}
for(int i=0;i<n;i++)
{
for(auto [y,c] : adj[i])
{
dp[i][0][y-(y/k)*k] = c;
}
}
for(int b=1;b<=LOG;b++)
{
for(int i=0;i<n && (i/k) + (1<<b) <= n/k;i++)
{
for(int j=0;j<k && ((i/k) + (1<<b))*k + j < n;j++)
{
for(int j1=0;j1<k;j1++)
{
dp[i][b][j] = min(dp[i][b][j], dp[i][b-1][j1] + dp[((i/k) + (1<<(b-1)))*k + j1][b-1][j]);
}
}
}
}
while(q--)
{
int x,y;
cin >> x >> y;
if(x/k == y/k)
{
cout << -1 << '\n';
}
else
{
vector<int> dist(k,1e9);
vector<int> pos(k,0);
pos[0] = x;
dist[0] = 0;
for(int b=LOG;b>=0;b--)
{
int curr = pos[0]/k;
if(curr + (1<<b) <= y/k)
{
vector<int> dist1(k,1e9);
vector<int> pos1(k,0);
for(int i=0;i<k;i++)
{
if((curr + (1<<b)) * k + i < n)
{
pos1[i] = (curr + (1<<b)) * k + i;
}
for(int j=0;j<k && (curr + (1<<b)) * k + j < n;j++)
{
dist1[j] = min(dist1[j],dist[i] + dp[pos[i]][b][j]);
}
}
dist = dist1;
pos = pos1;
}
}
if(dist[y-(y/k)*k] == 1e9)
{
cout << -1 << '\n';
}
else
{
cout << dist[y-(y/k)*k] << '\n';
}
}
}
}
