/*
Krishbansal333
Created: 08.01.2025 19:56:12
*/
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
#define ll long long
#define ld long double
#define ull uint_fast64_t
#define all(v) v.begin(),v.end()
#define maxi(v) max_element(all(v))
#define mini(v) min_element(all(v))
#define f(i,n) for(ll i = 0; i < n; i++)
#define vi vector<ll>
#define ipa(arr) for(ll i = 0; i < sizeof(arr)/sizeof(arr[0]); i++) cin>>arr[i];
#define ipv(arr) for(ll i = 0; i < (int) arr.size(); i++) cin>>arr[i];
#define line cout<<endl;
#define nl "\n"
#define mp map<ll,ll>
#define st set<ll>
#define pii pair<ll,ll>
#define vv vector<vector<ll>>
#define vvpi vector<vector<pair<ll,ll>>>
#define vpi vector<pair<ll,ll>>
#define pb push_back
#define F first
#define S second
#define fr(i,k,n) for(ll i = k; i < n; i++)
#define fv(i,k,n) for(ll i = n-1; i >=k; i--)
#define nah cout<<"NO\n";return;
#define naah cout<<"-1\n";return;
#define yeah cout<<"YES\n";return;
const ll MOD = 1e9+7;
const ll MOD2 = 998244353;
const ll INF = 1e16;
const ll MAXN = 10000001;
const ld PI = acos((ld)-1);
using namespace std;
//using namespace __gnu_pbds;
vector<ll> spf;
vector<ll> phi;
#ifndef ONLINE_JUDGE
#define debug(x) cout << endl << #x<<" "; _print(x); cout << endl;
#define debuga(x,a) cout << endl << #x<<" [ "; for(ll i=0 ; i <a; i++) { _print(x[i]); cout<<" "; } cout<<"]"<<endl;
#else
#define debug(x)
#define debuga(x,a)
#endif
void _print(ll t) {cout << t;}
void _print(int t) {cout << t;}
void _print(string t) {cout << t;}
void _print(char t) {cout << t;}
void _print(ld t) {cout << t;}
void _print(double t) {cout << t;}
void _print(ull t) {cout << t;}
template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cout << "{"; _print(p.F); cout << ","; _print(p.S); cout << "}";}
template <class T> void _print(vector <T> v) {cout << "[ "; for (T i : v) {_print(i); cout << " ";} cout << "]";}
template <class T> void _print(set <T> v) {cout << "[ "; for (T i : v) {_print(i); cout << " ";} cout << "]";}
template <class T> void _print(multiset <T> v) {cout << "[ "; for (T i : v) {_print(i); cout << " ";} cout << "]";}
template <class T, class V> void _print(map <T, V> v) {cout << "[ "; for (auto i : v) {_print(i); cout << " ";} cout << "]";}
// struct chash { const uint64_t C = uint64_t(2e18 * PI) + 71; const uint32_t RANDOM = chrono::steady_clock::now().time_since_epoch().count(); size_t operator()(uint64_t x) const { return __builtin_bswap64((x ^ RANDOM) * C); }};
ll interact(ll a, ll b)
{
cout << "? " << a << " " << b << endl; cout.flush();
ll res = 0; cin >> res ; return res;
}
ll cdiv(ll a,ll b)
{
return (a + b - 1) / b;
}
// **phii**
void phii(ll n) {
phi.assign(n + 1LL,0);
phi[0] = 0;
phi[1] = 1;
for (int i = 2; i <= n; i++)
phi[i] = i - 1;
for (int i = 2; i <= n; i++)
for (int j = 2 * i; j <= n; j += i)
phi[j] -= phi[i];
}
// **phii**
//**SIEVE**
// Time Complexity : O(nloglogn)
void sieve(ll n)
{
spf.assign(n+1,1);
spf[0] = 0;
for (ll i = 2; i <= n; i++) {
if (spf[i] == 1) {
for (ll j = i; j <= n; j += i) {
if (spf[j]== 1)
spf[j] = i;
}
}
}
}
vector<ll> getFactorization(ll x)
{
vector<ll> ret;
while (x != 1) {
ret.push_back(spf[x]);
x = x / spf[x];
}
return ret;
}
//**SIEVE**
//**FIBONACCI NUMBBERS**
struct matrix {
long long mat[2][2];
matrix friend operator *(const matrix &a, const matrix &b){
matrix c;
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
c.mat[i][j] = 0;
for (int k = 0; k < 2; k++) {
c.mat[i][j] += a.mat[i][k] * b.mat[k][j];
}
}
}
return c;
}
};
matrix matpow(matrix base, long long n) {
matrix ans{ {
{1, 0},
{0, 1}
} };
while (n) {
if(n&1)
ans = ans*base;
base = base*base;
n >>= 1;
}
return ans;
}
long long fib(int n) {
matrix base{ {
{1, 1},
{1, 0}
} };
return matpow(base, n).mat[0][1];
}
//**FIBONACCI NUMBBERS**
//**BINNARY EXPOO**
long long binpow(long long a, long long b, ll m) {
long long res = 1;
while (b > 0) {
if (b & 1)
{
res = (res * a);
if(res>=m) res = res%m+m;
}
a =(a * a);
if(a>=m) a=a%m+m;
b >>= 1;
}
return res%m;
}
long long binpow(long long a, long long b) {
long long res = 1;
while (b > 0) {
if (b & 1)
{
res = (res * a);
}
a =(a * a);
b >>= 1;
}
return res;
}
//**BINNARY EXPOO**
//**Mat power**
typedef vector<vector<ll>> Matrix;
Matrix mult(Matrix &a, Matrix &b)
{
ll n = a.size();
ll m = b[0].size();
ll p = b.size();
Matrix result(n,vi(m,0));
f(i,n)
f(j,m)
f(k,p)
result[i][j] = (result[i][j] + (a[i][k]*b[k][j])%MOD)%MOD;
return result;
}
Matrix matpow(Matrix &matrix, ll n)
{
ll sz = matrix.size();
Matrix result(sz,vi(sz));
f(i,sz) result[i][i] = 1;
if (n == 0LL) return result;
if (n == 1LL) return matrix;
Matrix temp = matpow(matrix, n / 2LL);
result = mult(temp, temp);
if (n % 2LL == 1LL) result = mult(result, matrix);
return result;
}
//**Mat power**
//**Unionfind**
struct dsu{
vector <int> root, sz;
int n;
dsu(int nn){
n = nn;
root.resize(n + 1);
sz.resize(n + 1, 1);
for (int i = 1; i <= n; i++) root[i] = i;
}
int find(int x){
if (root[x] == x) return x;
return root[x] = find(root[x]);
}
bool unite(int x, int y){
x = find(x); y = find(y);
if (x == y) return false;
if (sz[y] > sz[x]) swap(x, y);
sz[x] += sz[y];
root[y] = x;
return true;
}
};
struct unionFind
{
vector<int> p,score,lzy;
vector<vi> rank;
unionFind(int n)
{
rank.assign(n,vi()); p.assign(n,0);score.assign(n,0);lzy.assign(n,0);
iota(p.begin(),p.end(),0);
f(i,n) rank[i].push_back(i);
}
int findSet(int i){ return (p[i] == i) ? i :p[i] = findSet(p[i]);}
bool isSameSet(int i, int j){ return findSet(i) == findSet(j);}
void add(ll i, ll v)
{
ll x =findSet(i);
lzy[x] +=v;
}
ll get(ll i)
{
int x = findSet(i);
return score[i]+lzy[x];
}
void unionSet(int i, int j)
{
int x = findSet(i), y = findSet(j);
if(x==y) return;
if(rank[x].size() > rank[y].size()) {
p[y] = x;
for(auto i:rank[y])
{
rank[x].push_back(i);
}
for(auto i:rank[y])
{
score[i]+=lzy[y]-lzy[x];
}
lzy[y] =0;
rank[y].clear();
}
else
{
p[x] = y;
for(auto i:rank[x])
{
rank[y].push_back(i);
}
for(auto i:rank[x])
{
score[i]+=lzy[x]-lzy[y];
}
lzy[x] =0;
rank[x].clear();
}
}
};
//**Unionfind**
//**Segtree**
struct segtree {
// to reduce memory, use left node as v + 1, right node as v + (mid - l + 1) << 1
struct node {
ll val = 0;
node() : val(0ll) {}
node(ll val_) : val(val_) {}
node operator+(const node &a) {
return {this -> val + a.val};
}
};
int n;
vector<ll> a; vector<node> sgt;
// segtree(int n_) : n(n_), sgt(vector(n_ << 2, node())), a(vector(n_, 0ll)) {}
segtree(vector<ll> a_) {
n = a_.size();
sgt.resize(n << 2), a = a_;
auto build = [&](int v, int tl, int tr, auto self) -> void
{
if(tl == tr) sgt[v] = apply(a[tl]);
else {
int tm = (tl + tr) >> 1;
self(v << 1, tl, tm, self); self((v << 1) | 1, tm + 1, tr, self);
sgt[v] = sgt[v << 1] + sgt[(v << 1) | 1];
}
};
build(1, 0, n - 1, build);
}
node rquery(int v, int tl, int tr, int l, int r) {
if(tl == l && tr == r) return sgt[v];
else if(l > r) return def();
else{
int tm = (tl + tr) >> 1;
node leftans = rquery(v << 1, tl, tm, l, min(tm, r));
node rightans = rquery((v << 1) | 1, tm + 1, tr, max(l, tm + 1), r);
return leftans + rightans;
}
}
void pupdate(int v, int tl, int tr, int pos, ll x) {
if(tl == tr)
sgt[v] = apply(x);
else{
int tm = (tl + tr) >> 1;
if(pos <= tm) pupdate(v << 1, tl, tm, pos, x);
else pupdate((v << 1) | 1, tm + 1, tr, pos, x);
sgt[v] = sgt[v << 1] + sgt[(v << 1) + 1];
}
}
ll query(int l, int r) {
return rquery(1, 0, n - 1, l, r).val;
}
void update(int i, ll x){
pupdate(1, 0, n - 1, i, x);
}
static node apply(ll val) {
return node(val);
}
node def() {
return node(0);
}
};
//**Segtree**
//** lazy segtree **
struct segtreelazy {
struct node {
// edit this
ll val = 0;
ll lazy = 0;
node() : val(0ll), lazy(0ll) {}
node(ll val_, ll lazy_) : val(val_), lazy(lazy_) {}
node operator+(const node &a) {
return { this -> val + a.val, 0ll };
}
};
int n;
vector<ll> a; vector<node> sgt;
segtreelazy(vector<ll> a_) {
n = a_.size();
sgt.resize(n << 2), a = a_;
auto build = [&](int v, int tl, int tr, auto self) -> void {
if(tl == tr) sgt[v] = apply(a[tl]);
else {
int tm = (tl + tr) >> 1;
self(v << 1, tl, tm, self); self((v << 1) | 1, tm + 1, tr, self);
sgt[v] = sgt[v << 1] + sgt[(v << 1) | 1];
}
};
build(1, 0, n - 1, build);
}
node rquery(int v, int tl, int tr, int l, int r) {
if(tl == l && tr == r) return sgt[v];
else if(l > r) return def();
else{
push(v);
int tm = (tl + tr) >> 1;
node leftans = rquery(v << 1, tl, tm, l, min(tm, r));
node rightans = rquery((v << 1) | 1, tm + 1, tr, max(l, tm + 1), r);
return leftans + rightans;
}
}
void rupdate(int v, int tl, int tr, int l, int r, ll x) {
if(tl == l && tr == r)
upd(v, x);
else if(l <= r){
push(v);
int tm = (tl + tr) >> 1;
rupdate(v << 1, tl, tm, l, min(r, tm), x);
rupdate((v << 1) | 1, tm + 1, tr, max(l, tm + 1), r, x);
sgt[v] = sgt[v << 1] + sgt[(v << 1) + 1];
}
}
ll query(int l, int r) {
return rquery(1, 0, n - 1, l, r).val;
}
void update(int l, int r, ll x){
rupdate(1, 0, n - 1, l, r, x);
}
void push(int v) {
upd(v << 1, sgt[v].lazy); upd((v << 1) | 1, sgt[v].lazy);
sgt[v].lazy = 0;
}
void upd(int v, ll x) {
// edit this
// do not forget to update lazy here ( sgt[v]+=x )
sgt[v].val += x;
sgt[v].lazy += x;
}
static node apply(ll val) {
// edit this;
return node(val, 0ll);
}
node def() {
// edit this
return node(0ll, 0ll);
}
};
//** lazy segtree **
//**lca**
ll k;
//**lca**
struct node
{
ll val;
vv mat;
node() {
val = 0;
mat.assign(k,vi(k,INF));
}
};
//Add Modulo.
void solve(){
ll n=0,m,d,x,y,z;bool b,flag; string s; mp mm; st se; vi v;
cin>>k>>n>>m>>d;
vvpi graph(n+1);
f(i,m)
{
cin>>x>>y>>z;
graph[x].pb({y,z});
}
ll sz = ceil((n+1)*1.0/k);
ll l = ceil(log2(sz+1));
vector<vector<node>> up(sz+1,vector<node>(l+1));
auto combine=[&](node& a, node& b)->node
{
node ans;
ans.val = b.val;
vv mat(k,vi(k,INF));
f(i,k)
{
f(j,k)
{
ll res = INF;
f(p,k)
{
res = min(res,a.mat[i][p]+b.mat[p][j]);
}
mat[i][j]=res;
}
}
ans.mat =mat;
return ans;
};
fv(i,0,sz-1)
{
vv mat(k,vi(k,INF));
f(j,k)
{
for(auto [x,y]:graph[i*k+j])
{
mat[j][x%k] = min(y,mat[j][x%k]);
}
}
node kri;
kri.val = i+1;
kri.mat = mat;
up[i][0] = kri;
for (int j = 1; j <= l; ++j)
{
up[i][j] = combine(up[i][j-1],up[(up[i][j-1].val)][j-1]);
}
}
// debug(up);
while(d--)
{
cin>>x>>y;
ll lg=x/k,rg=y/k;
ll lv=x%k,rv=y%k;
if(y<x) {cout<<"-1\n";continue;}
if(rg==lg && lv!=rv) {cout<<"-1\n";continue;}
ll res =0;
node curr;
curr.val = lg;
curr.mat.assign(k,vi(k,0));
for (int i = l; i >= 0; --i) {
if(curr.val + pow(2,i) <= rg)
{
curr = combine(curr,up[curr.val][i]);
}
}
// debug(curr.val)
cout<<((curr.mat[lv][rv] >= INF-100000) ? -1:curr.mat[lv][rv] )<<endl;
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// memset(dp,-1,sizeof(dp));
ll t =1;
// cin>>t;
while(t--){
solve();
}
return 0;
}
