// Born_To_Laugh - Hughie Do
#include <bits/stdc++.h>
#define alle(AC) AC.begin(), AC.end()
#define fi first
#define se second
using namespace std;
typedef long long ll;
[[maybe_unused]] const ll MOD = 998244353, INF = 3e18 + 7;
const int maxn = 5e4 + 10;
int k, n, m, q;
vector<pair<int,int>> adj[maxn];
vector<vector<vector<vector<ll>>>> dp;
ll ope(int a, int b){
vector<ll> dist(k + 1, 0);
int cur = a / k;
int sth = b / k - a / k;
if(sth <= 0)return -1;
for(int j=0; j<20; ++j){
if(sth & (1 << j)){
vector<ll> nxt = dist;
for(int x = 0; x < k; ++x){
ll val = INF;
for(int y = 0; y < k; ++y){
val = min(val, dist[y] + dp[cur][j][y][x]);
}
nxt[x] = val;
}
dist = nxt;
cur += (1 << j);
}
}
if(dist[b % k] < INF)return dist[b % k];
else return -1;
}
void solve(){
cin >> k >> n >> m >> q;
dp.assign(
(int)n / k + 1,
vector<vector<vector<ll>>> (
20,
vector<vector<ll>> (
k + 1,
vector<ll> (
k + 1,
INF
)
)
)
);
for(int i=1; i<=m; ++i){
int a, b, c;cin >> a >> b >> c;
adj[a].push_back({b, c});
dp[a / k][0][a % k][b % k] = c;
// cout << a / k << ' ' << 0 << ' ' << a % k << ' ' << b % k << ' ' << c << " ?? \n";
}
for(int i=(int)n / k; i>=0; --i){
for(int j=1; j<20; ++j){
if(i + (1 << j) > int(n / k))break;
for(int x = 0; x < k; ++x){
for(int y = 0; y < k; ++y){
for(int z = 0; z < k; ++z){
dp[i][j][x][y] = min(
dp[i][j][x][y],
dp[i][j - 1][x][z] + dp[i + (1 << (j - 1))][j - 1][z][y]
);
}
// cout << i << ' ' << j << ' ' << x << ' ' << y << ' ' << dp[i][j][x][y] << '\n';
}
}
}
}
while(q--){
int a, b;cin >> a >> b;
cout << ope(a, b) << '\n';
}
}
signed main(){
// freopen("inp.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
solve();
}
