#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define FOR(i , a , b) for(int i = (a) , _b = (b); i <= _b; ++i)
#define MASK(x) ((LL)(1) << (x))
#define BIT(mask , x) (((mask)>>(x))&(1))
#define sz(x) (int)(x).size()
template<class T1 , class T2>
bool maximize(T1 &a , T2 b){
if (a < b) return a = b , true; else return false;
}
template<class T1 , class T2>
bool minimize(T1 &a , T2 b){
if (a > b) return a = b , true; else return false;
}
template<class T>
void compress(vector<T>&data){
sort(data.begin() ,data.end());
data.resize(unique(data.begin() , data.end()) - data.begin());
}
template<class T1 , class T2>
T2 Find(const vector<T1>&data , T2 y){
return upper_bound(data.begin() , data.end() , y) - data.begin();
}
const int N = (int) 5e4;
const int inf = (int) 1e9 + 7;
const int MAXLOG = (int) 16;
const int MAXK = (int) 5;
int dp[N + 2][MAXLOG + 2][MAXK + 2][MAXK + 2];
int n , m , q , k;
void combine(int res[MAXK+2][MAXK+2] , int x[MAXK+2][MAXK+2] , int y[MAXK+2][MAXK+2]){
for(int t = 0; t <= k; ++t){
for(int i = 0; i <= k; ++i){
for(int j = 0; j <= k; ++j){
minimize(res[i][j] , x[i][t] + y[t][j]);
}
}
}
return ;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0) ; cout.tie(0) ;
#define name "main"
if (fopen(name".inp","r")){
freopen(name".inp","r",stdin);
freopen(name".out","w",stdout);
}
cin >> k >> n >> m >> q;
memset(dp , 0x3f , sizeof dp);
for(int i = 1; i <= m; ++i){
int a , b , w;
cin >> a >> b >> w;
minimize(dp[a / k][0][a % k][b % k] , w);
}
int tt = (n / k) + (n % k != 0);
for(int j = 1; j <= MAXLOG; ++j){
for(int i = 0; i + MASK(j) - 1 <= tt; ++i){
combine(dp[i][j] , dp[i][j - 1] , dp[i + MASK(j - 1)][j - 1]);
}
}
while(q--){
int a , b; cin >> a >> b;
int ans[MAXK + 2][MAXK + 2] = {};
int tmp[MAXK + 2][MAXK + 2] = {};
int cur = a / k;
memset(ans,0x3f,sizeof ans);
for(int i = 0; i <= MAXK; ++i) ans[i][i] = 0;
for(int i = MAXLOG; i >= 0; --i){
if (cur + MASK(i) <= b / k){
memset(tmp,0x3f,sizeof tmp);
combine(tmp , ans , dp[cur][i]);
for(int j = 0; j <= k; ++j){
for(int t = 0; t <= k; ++t) ans[j][t] = tmp[j][t];
}
cur += MASK(i);
}
}
LL res = inf;
minimize(res , ans[a%k][b%k]);
if (res == inf) res = -1;
cout << res << '\n';
}
return 0;
}
