#include <cstdio>
#include <stdio.h>
#include <stdbool.h>
#include <iostream>
#include <map>
#include <vector>
#include <climits>
#include <stack>
#include <string>
#include <queue>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <cctype>
#include <bitset>
#include <iomanip>
#include <cstring>
#include <numeric>
#include <cassert>
using namespace std;
#define int long long
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
int n, k;
vector<vector<pii> > graph;
vector<vector<int> > combine(vector<vector<int> > a, int r, vector<vector<int> > b){
vector<vector<int> > dp(5, vector<int>(5, LLONG_MAX/100000));
for (int node=r*k; node<min(n, (r+1)*k); ++node)for (auto num:graph[node])for (int i=0; i<k; ++i)for (int j=0; j<k; ++j)dp[i][j]=min(dp[i][j], a[i][node%k]+b[num.fi%k][j]+num.se);
return dp;
}
struct node{
int s, e, m;
vector<vector<int> > dp;
node *l, *r;
node(int S, int E){
s = S, e = E, m = (s+e)/2;
if (s!=e){
l = new node(s, m);
r = new node(m+1, e);
dp=combine(l->dp, m, r->dp);
}
else{
dp.resize(5, vector<int>(5, LLONG_MAX/100000));
for (int i=0; i<k; ++i)dp[i][i]=0;
}
}
vector<vector<int> > query(int left, int right){
if (s==left && e==right)return dp;
if (right<=m)return l->query(left, right);
else if (left>m)return r->query(left, right);
else return combine(l->query(left, m), m, r->query(m+1, right));
}
}*st;
int32_t main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int m, q, a, b, c;
cin>>k>>n>>m>>q;
graph.resize(n);
while (m--)cin>>a>>b>>c, graph[a].pb(mp(b, c));
st = new node(0, (n-1)/k);
while (q--){
cin>>a>>b;
int res=st->query(a/k, b/k)[a%k][b%k];
cout<<(res==LLONG_MAX/100000?-1:res)<<"\n";
}
}
