#include <iostream>
#include <algorithm>
using namespace std;
const int N = 50005, inf = 2e9;
struct mat{
int dst[5][5];
mat(){
for (int i=0;i<5;i++)
for (int j=0;j<5;j++)
dst[i][j] = inf;
}
mat operator *(mat Nw){
mat res;
for (int k=0;k<5;k++){
for (int i=0;i<5;i++)
for (int j=0;j<5;j++)
res.dst[i][j] = min(res.dst[i][j], dst[i][k] + Nw.dst[k][j]);
}
return res;
}
} Mn[N][20];
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int k, n, m, o;
cin>>k>>n>>m>>o;
for (int i=1, a, b, c;i<=m;i++){
cin>>a>>b>>c;
Mn[a / k][0].dst[a % k][b % k] = c;
}
n /= k;
for (int i=n;i>=0;i--){
for (int j=0;i + (1<<j) <= n;j++)
Mn[i][j+1] = Mn[i][j] * Mn[i + (1<<j)][j];
}
for (int i=1, a, b;i<=o;i++){
cin>>a>>b;
if (b / k <= a / k){
cout<<-1<<'\n';
continue;
}
int d = b / k - a / k - 1, cur = a / k + 1;
mat Now = Mn[a / k][0];
for (int i=0;i<17;i++){
if ((1<<i) & d)
Now = Now * Mn[cur][i], cur += (1<<i);
}
if (Now.dst[a % k][b % k] == 1e9)
cout<<-1<<'\n';
else
cout<<Now.dst[a % k][b % k]<<'\n';
}
}
