#include<bits/stdc++.h>
#define ui unsigned int
#define ll long long
using namespace std;
const int MAXN=2e5+5;
struct Edge { int v; ui w; };
struct Node {
	ll d; int u,i;
	friend bool operator <(const Node &x,const Node &y) { return x.d>y.d; }
};
vector <Edge> gs[MAXN],gt[MAXN];
ll ds[MAXN],dt[MAXN];
bool vs[MAXN],vt[MAXN];
ll qry(int s,int t) {
	if(s==t) return 0;
	if(gs[s].empty()||gt[t].empty()) return -1;
	vector <int> us{s},ut{t}; ds[s]=dt[t]=0,vs[s]=vt[t]=1;
	priority_queue <Node> qs,qt;
	qs.push({gs[s][0].w,s,0}),qt.push({gt[t][0].w,t,0});
	int z=0;
	while(qs.size()&&qt.size()) {
		ll d; int u,i,v;
		if(qs.size()<=qt.size()) {
			d=qs.top().d,u=qs.top().u,i=qs.top().i,v=gs[u][i].v,qs.pop();
			if(i+1<(int)gs[u].size()) qs.push({ds[u]+gs[u][i+1].w,u,i+1});
			if(vs[v]) continue;
			vs[v]=true,ds[v]=d,us.push_back(v);
			if(vt[v]) { z=v; break; }
			if(gs[v].size()) qs.push({d+gs[v][0].w,v,0});
		} else {
			d=qt.top().d,u=qt.top().u,i=qt.top().i,v=gt[u][i].v,qt.pop();
			if(i+1<(int)gt[u].size()) qt.push({dt[u]+gt[u][i+1].w,u,i+1});
			if(vt[v]) continue;
			vt[v]=true,dt[v]=d,ut.push_back(v);
			if(vs[v]) { z=v; break; }
			if(gt[v].size()) qt.push({d+gt[v][0].w,v,0});
		}
	}
	if(!z) return -1;
	ll ans=ds[z]+dt[z];
	for(int u:us) {
		ll lim=(ds[z]-ds[u])<<1;
		for(auto e:gs[u]) {
			if(e.w>=lim) break;
			if(vt[e.v]) ans=min(ans,ds[u]+e.w+dt[e.v]);
		}
	}
	for(int u:ut) {
		ll lim=(dt[z]-dt[u])<<1;
		for(auto e:gt[u]) {
			if(e.w>=lim) break;
			if(vs[e.v]) ans=min(ans,ds[e.v]+e.w+dt[u]);
		}
	}
	for(int u:us) vs[u]=false;
	for(int u:ut) vt[u]=false;
	return ans;
}
signed main() {
	ios::sync_with_stdio(false);
	int n,m,q; ui sd; cin>>n>>m>>q>>sd;
	mt19937 rnd(sd);
	auto ver=[&]() {
		static const ui LIM=-1u/n*n;
		ui x; for(x=rnd();x>=LIM;x=rnd());
		return x%n+1;
	};
	for(int i=1;i<=m;++i) {
		int u=ver(),v=ver(); ui w=rnd();
		gs[u].push_back({v,w});
		gt[v].push_back({u,w});
	}
	for(int i=1;i<=n;++i) {
		sort(gs[i].begin(),gs[i].end(),[&](auto x,auto y){ return x.w<y.w; });
		sort(gt[i].begin(),gt[i].end(),[&](auto x,auto y){ return x.w<y.w; });
	}
	for(int i=1,s,t;i<=q;++i) {
		cin>>s>>t,cout<<qry(s,t)<<"\n";
		if(i==42) cout<<"!! "<<s<<" "<<t<<"\n";
	}
	return 0;
}