#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pii;
const ll inf = 1e18;
const int i_inf = 1e9;
const ll mod = 1e9+7;
mt19937 _rand(time(NULL));
const int mxn = 2e5;
int n, k, m, q;
vector<pii> g[mxn];
ll sparse[mxn][17][5][5];
ll aux[5][5];
void fillaux(int u, int p){
fr(i, 0, k){
fr(j, 0, k){
aux[i][j] = inf;
}
}
fr(i, 0, k){
fr(j, 0, k){
ll w = sparse[u][p][i][j];
int pos = (u+(1<<p)-1)*k + j;
for(auto v : g[pos]){
int jp = v.st%k;
aux[i][jp] = min(aux[i][jp], w + v.nd);
}
}
}
}
void combine(int u, int p){
int subu = u;
int subv = u + (1<<p);
fr(mid, 0, k){
fr(i, 0, k){
fr(j, 0, k){
sparse[subu][p+1][i][j] = min(sparse[subu][p+1][i][j], aux[i][mid] + sparse[subv][p][mid][j]);
}
}
}
}
void update(int u, int p){
if(u + (1<<p) > n) return;
fillaux(u, p-1);
combine(u, p-1);
}
ll dist[5];
ll dist2[5];
ll query(int a, int b){
int S = a/k;
int E = b/k;
if(S == E) return -1;
fr(i, 0, k) dist[i] = inf;
dist[a%k] = 0;
for(int p = 16; p >= 0; p --){
while(S + (1<<p) <= E){
fr(i, 0, k) dist2[i] = inf;
fr(i, 0, k){
fr(j, 0, k){
ll w = sparse[S][p][i][j];
int pos = (S+(1<<p)-1)*k + j;
for(auto v : g[pos]){
int jp = v.st%k;
dist2[jp] = min(dist2[jp], dist[i] + w + v.nd);
}
}
}
fr(i, 0, k) dist[i] = dist2[i];
S += (1<<p);
}
}
if(dist[b%k] == inf) return -1;
else return dist[b%k];
}
void solve(){
cin >> k >> n >> m >> q;
while(n % k != 0) ++n;
fr(i, 0, m){
int u, v, w;
cin >> u >> v >> w;
g[u].pb({v, w});
}
fr(u, 0, n/k){
fr(p, 0, 17){
fr(i, 0, k){
fr(j, 0, k){
sparse[u][p][i][j] = inf;
}
}
}
}
fr(u, 0, n/k){
fr(i, 0, k){
sparse[u][0][i][i] = 0;
}
}
fr(p, 1, 17){
fr(u, 0, n/k){
update(u, p);
}
}
while(q--){
int a, b;
cin >> a >> b;
cout<<query(a, b)<<endl;
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
}
