#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using table = vector<vector<int>>;
i64 k,n,m,q;
table a[50009],seg[2000009];
vector<pair<int,int>> adj[50009];
table NotMul(const table& x,const table& y)
{
table z(x.size(),vector<int>(y.back().size(),(int)1e9));
for(int i=0;i<x.size();++i)
{
for(int t=0;t<y.size();++t)
{
for(int j=0;j<y[i].size();++j)
z[i][j]=min(z[i][j],x[i][t]+y[t][j]);
}
}
return z;
}
void build(int node,int l,int r)
{
if(l==r) seg[node]=a[l];
else
{
build(2*node,l,(l+r)/2);
build(2*node+1,(l+r)/2+1,r);
seg[node]=NotMul(seg[2*node],seg[2*node+1]);
}
}
table get(int node,int tl,int tr,int l,int r)
{
if(tr<l or r<tl) return a[0];
if(l<=tl and tr<=r) return seg[node];
return NotMul(get(2*node,tl,(tl+tr)/2,l,r),get(2*node+1,(tl+tr)/2+1,tr,l,r));
}
int main()
{
if(fopen("D:/CPP/THEMIS/test.inp","r"))
{
freopen("D:/CPP/THEMIS/test.inp","r",stdin);
freopen("D:/CPP/THEMIS/test.out","w",stdout);
}
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>k>>n>>m>>q;
for(int u,v,w,i=1;i<=m;++i)
{
cin>>u>>v>>w;
adj[u].push_back({v,w});
}
for(int i=0;i<=n/k+3;++i) a[i].assign(k,vector<int>(k,int(1e9)));
for(int j=0;j<k;++j) a[0][j][j]=0;
for(int i=0;k*i<n;++i)
{
for(int j=0;j<k;++j)
{
for(auto& v:adj[j+k*i])
a[i+1][j][v.first%k]=v.second;
}
}
build(1,1,n/k);
for(int u,v;q>0;--q)
{
cin>>u>>v;
if(u>v) cout<<"-1\n";
else if(u==v) cout<<"0\n";
else if(u/k==v/k) cout<<"-1\n";
else
{
int res=get(1,1,n/k,u/k+1,v/k)[u%k][v%k];
cout<<(res<int(1e9)?res:-1)<<'\n';
}
}
}
/*
........................
..::-+**#%@@@@@@@@@@@@@@@@@@%#**+::..
..:=++#%%@@@@@@@@@@@@@@@@%%%%%%%%%@@@@@@@@@@@@%+.
..:-+*#%@@@@@@@@%%%%##############################%%@@@@*:.
..:-+*%@@@@@@@%%%##########################################%@@@@+:.
..:=+%@@@@@@%%#####################################################@@@@+..
....-+%@@@@@@%#############################################################@@@@=..
..=#@@@@@%%###################################################################%@@@%-.
.:+#%@@@@%%#########################################################################%@@@#:.
.:=*%@@@%%###############################################################################%@@@@-.
..-*%@@@%%#####################################################################################%@@@=.
..+@@@@###########################################################################################%@@@*..
.*@@@#*##############################################################################################@@@%.
.+@@@#**################################################################################################@@@%:.
.-%@@#**####%##############################################################################################%@@%:.
.+@@#***###%%################################################################################################%@@@-.
:#@%****###%%*#################################################################################################%@@@-.
-@@%****###@%*###################################################################################################%@@@-.
-@@#***###%@#*#####################################################################################################%@@@=.
-@@#***###@@#*#######################################################################################################@@@%-.
:@@#***###@%**#########################################################################################################@@@+.
:%@#***##%@%**##########################################################################################################%@@@.
.#@%***##%@%**############################################################################################################%@@*.
.+@%***##@@#**##############################################################################################@@##############@@@:.
:@@***##@@#**###############################################################################################@@@%############%@@#.
.%@#***#@@#**####################################%@@%#######################################################@@@@@@############@@@=.
.*@%***%@@#***##################################%@@@@@@@%###################################################%@@@@@@@############@@%.
-@@***%@@#***##################################@@@@@@@@@@@%#################################################@@@@@@@@@###########@@@=.
.#@#**#@@#****################################%@@@@@@@@@@@@@@@%#############################################%@@@@@@@@@@###########@@%.
=@%**#@@%****################################@@@@@@@@@@@@@@@@@@@%###########################################@@@@@@@@@@@@##########%@@=.
.@@**#@@%*****##############################%@@@@@@@@@@@@@@@@@@@@@@@########################################@@@@@@@@@@@@@@##########@@%.
.#@###@@%*****##############################@@@@@@@@@@@@@@@@@@@@@@@@@@@#####################################@@@@@@@@@@@@@@@@#########@@@-
..#@###%@@******############################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@##################################%@@@@@@@@@@@@@@@@@#########@@#.
.-%@###%@@#*****############################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@###############################%@@@@@@@@@@@@@@@@@@@########@@@:.
...-%@%####@@#******###########################@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%############################%@@@@@@@@@@@@@@@@@@@@%#######%@@*.
..:+%@@######%@%******###########################@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%##########################@@@@@@@@@@@@@@@@@@@@@@%#######@@@.
.#@%%%##########@@*******#########################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%######################%@@@@@@@@@@@@@@@@@@@@@@@@%######%@@+.
:#@%##########@@#******#########################@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@####################%@@@@@@@@@@@@@@@@@@@@@@@@@@#######@@%.
.+%@%#######%@%*******########################@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%#################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@######%@@-.
.+%@@%####@@#******#######################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@###############%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@######@@#.
.:*%@@@@@%*******######################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#############@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%#####%@@:.
.....-@@********#####################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%#########%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%#####@@*.
.=@%*******#####################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#######@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#####@@@.
.%@#*******####################@@@@@@@@@@@@@@@@@@@@@@@@@@%##*******##%@@@@@@@@@@@@@@@@@@@@@@####%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#####@@=.
.+@@********###################@@@@@@@@@@@@@@@@@@@@@@#*=:...............:=*#@@@@@@@@@@@@@@@@@@#%@@@@@@@@@@@@@@#*+-:.......:-=+#%@@@@@@@@@%####@@%.
.@@%*******###################@@@@@@@@@@@@@@@@@@@@#-.........................-*%@@@@@@@@@@@@@@@@@@@@@@@@@@%*-....................=#@@@@@@@#####@@=.
.+@@********##################@@@@@@@@@@@@@@@@@@@=...............................-%@@@@@@@@@@@@@@@@@@@@@@%-..........................=@@@@@@####@@%.
:@@@********#################@@@@@@@@@@@@@@@@@@=...................................-@@@@@@@@@@@@@@@@@@@@-..............................+@@@@%####@@+.
.*@@#********################%@@@@@@@@@@@@@@@@#:..........................:=+++=:....:*@@@@@@@@@@@@@@@@*:....:=+++=:.....................:%@@@####%@@:.
:@@@********################%@@@@@@@@@@@@@@@@*...........................=*#%%%#*=.....+@@@@@@@@@@@@@@=.....-*#%%%#*-.....................:#@@%####@@#.
.*@@%********###############%@@@@@@@@@@@@@@@@#...........................-*%@@@@@%*-.....*@@@@@@@@@@@@+.....-*%@@@@@#*-.....................:@@@####%@@*.
.=@@@*********###############@@@@@@@@@@@@@@@@@:...........................*=-@@@@@@#*.....:@@@@@@@@@@@@......*=+@@@@@@*+......................=@@@####@@@=.
-@@@**********##############@@@@@@@@@@@@@@@@@#............................*..+@@@@@#*......#@@@@@@@@@@*.....:*..#@@@@@#*......................:@@@%####@@@=.
.+@@@#**********#############%@@@@@@@@@@@@@@@@@*............................+-.%@@@@@*+......#@@@@@@@@@@+......*:.%@@@@@*+.......................@@@@#####@@@=.
.-%@@@***********##############@@@@@@@@@@@@@@@@@@#............................-*#@@@@@#*:......%@@@@@@@@@@+......=*#@@@@@#*:......................:@@@@%#####@@@+.
..=#@@@#************#############@@@@@@@@@@@@@@@@@@@@:............................-+*###*+:......:@@@@@@@@@@@#.......=*#%%#*+:.......................=@@@@@######@@@#.
...:=*@@@%#*************#############%@@@@@@@@@@@@@@@@@@@@*..............................:===:........#@@@@@@@@@@@@-.......:=++=-.........................%@@@@@@######@@@%-.
.-+*%@@@@%#****************#############@@@@@@@@@@@@@@@@@@@@@@=.........................................+@@@@@@@@@@@@@@:....................................#@@@@@@@#######%@@@*..
-@@%**********************#############%@@@@@@@@@@@@@@@@@@@@@@@+.......................................#@@@@@@@@@@@@@@@@:..................................#@@@@@@@@@########@@@@=.
.:%@%********************##############@@@@@@@@@@@@@@@@@@@@@@@@@%-...................................=@@@@@@@@@@@@@@@@@@@*...............................=@@@@@@@@@@@%########%@@@%+.
.+@@#******************##############@@@@@@@@@@@@@@@@@@@@@@@@@@@#=..............................:+%@@@@@@@@@@@@@@@@@@@@@%+:..........................=#@@@@@@@@@@@@@##########%@@@@*:.
.:%@@#****************#############%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%+-........................:=*@@@@@@@@@%%@@@@@@@@@@%@@@@@*-:....................-+@@@@@@@@@@@@@@@@%###########%@@@+.
.+@@%***************#############%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*=-:..............::-+#@@@@@@@%#+-:::-#@@@@@@#::-+#@@@@@#=-::.........::-=*@@@@@@@@@@@@@@@@@@@@##########%@@@+.
.#@@%*************#############@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#*++++++*#%@@@@@@@@@@%=:::::::::::+@@@=:::::::-#@@@@@@@@@%%%%%@@@@@@@@@@@@@@@@@@@@@@@@@@@%########%@@@=.
.-%@@%************############@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#=-:::::::::::::::-:::::::::::-=@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%#######@@@@-.
..=%@@%**********############@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@+-:::::::::::::::::::::::::::::::::=%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@######%@@@#:.
.=%@@%*********###########%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%=:::::::::::::::-+####=::::::::::::::::+@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%######@@@@=..
.=%@@%#*******############%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%=::::::::::::::::+#+-::=#*::::::::::::::::-#@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@######%@@@%-.
.=%@@@#******#############%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@+:::::::::::::::::*-:::::::*+:::::::::::::::::*@@@@@@@@@@@@@@@@@@@@@@@@@@@%######%@@@+..
.-%@@@%*****###############@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#::::::::::::::::::-::::::::::=::::::::::::::::::=@@@@@@@@@@@@@@@@@@@@@@@@@#######@@@@:.
..-#@@@@#***################@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@=::::::::::::::::::::::::::::::::::::::::::::::::::-@@@@@@@@@@@@@@@@@@@@@@%######@@@@+..
.:+@@@@%#**################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%-::::::::::::::::::::::::::::::::::::::::::::::::::::-@@@@@@@@@@@@@@@@@@@%######%@@@*:.
..=#@@@@#**################%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#:::::::::::::::::::::::::::::::::::::::::::::::::::::::=@@@@@@@@@@@@@@@@%######%@@@#-.
.:*%@@@%###################%@@@@@@@@@@@@@@@@@@@@@@@@@@*:::::::::::::::::::::::::::::::::::::::::::::::::::::::::+@@@@@@@@@@@@@%#######@@@%=..
.-#@@@@%###################%@@@@@@@@@@@@@@@@@@@@@@*:::::::::::::::::::::::::::::::::::::::::::::::::::::::::-=@@@@@@@@@@@%######%@@@%=..
...-%@@@@@####################@@@@@@@@@@@@@@@@@@@@+::::::::::::::::::::::::::::::::::::::::::::::::::::::-#@@@@@@@@@@@%######%@@@%-..
...-#@@@@@%###################%@@@@@@@@@@@@@@@@@@@#+:::::::::::::::::::::::::::::::::::::::::::::::+%@@@@@@@@@@@%######%@@@@*:..
..:-*@@@@@@%%##################%@@@@@@@@@@@@@@@@@@%#+=:::::::::::::::::::::::::::::::::::::=*#%@@@@@@@@@@@%######%@@@@@#=..
..-+#@@@@@@%%##################%%@@@@@@@@@@@@@@@@@@%*+==-:::::::::::::::::::::::-=+*#%@@@@@@@@@@@@@%######%@@@@@*-:..
..=#%@@@@@@%%###################%@@@@@@@@@@@@@@@@@@@@@%#*+===------===+*#%@@@@@@@@@@@@@@@@@@%######%@@@@@%*-.
..-*@@@@@@@@@%####################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%#######%@@@@@@#-..
.....=#@@@@@@@@@@%######################%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%%########%@@@@@@%+:...
..::=*%@@@@@@@@@@%%#######################%%%%%@@@@@@@@@@@@%%%%############%@@@@@@@%=:..
...-=+#%@@@@@@@@@@@@%%%##########################################%%@@@@@@%*=-:..
...:-+*#%@@@@@@@@@@@@@@%%%%%#########################%%%@@@@@@@%*=:..
...*@@%@@@@@@@@@@@@@@@@@@@@@@@%%%%%%####%%@@@@@@@@%#+:..
.*@@****#####%%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@#=:..
.@@%****##########@#====%%###@##@%%%@@@%-:....
-@@#****##########@#===+@#***@%=@%###@@%.
=@@*****##########%@===#@#***%@=%@###%@@-
.*@@*****###########@*==*%%%%%@@+@%###%@@+.
.@@%****############%@+=====++==%@#####@@%.
=@@#****#############@@========#@######@@@.
.*@@*****############@@%@+=====*@#######@@@=.
.%@@*****###########%@##@@#===#@########%@@*.
-@@%****###########%@%##@%%%*#@##########@@%.
=@@#****###########@%###@##%@@###########@@@-.
+@@*****##########@@###%@##%@@###########@@@+.
.%@@****##########@@####@%##%@@###########%@@%.
-@@%****#########@@#####@###%@@############@@@:
=@@#****########%@#####%@####@@############@@@=.
#@@*****#######%@######@%####@@############%@@#.
.%@@****#######%@######%@#####@@############%@@%.
-@@%****######%@#######%@#####@@%############@@@-.
=@@#****#####%@########@%#####@@%############@@@+.
+@@#****####%@########%@######@@%############%@@#.
.%@@****####%@#########@@######@@%############%@@@:
:@@%****###%@##########@%######@@%#############@@@=.
=@@%****##%%##########%@#######@@%#############@@@*.
#@@#****#%%###########@@#######@@@#############%@@%.
.%@@*****%############%@%#######@@@#############%@@@:
-@@@****##############@@########%@@##############@@@+.
-@@%****##############@%########%@@##############@@@#.
.*@@#****#############@@#########%@@##############%@@@:
.%@@*****#############@%#########%@@##############%@@@-.
:@@@*****############%@##########%@@###############@@@*.
-@@%*****############@%##########%@@###############@@@%.
#@@#****############%@############@@###############%@@@:
.%@@#****############@%############@@%###############@@@=.
:@@@*****###########%@#############@@%###############@@@*.
-@@%*****###########@%#############@@%###############@@@%.
=@@%*****##########%@##############@@%###############%@@@:
.#@@#*****##########@%##############@@%################@@@+.
:@@@*****###########@###############@@%################@@@#.
*/
