#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+10;
struct edge
{
	int v;
	unsigned w;
};
struct node
{
	ll d;
	int u,i;
	bool operator <(const node &b)const
	{
		return d>b.d;
	}
};
vector<edge>gs[N],gt[N];
int n,m,q;
ll ds[N],dt[N];
unsigned sd;
bool vs[N],vt[N];
ll query(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.empty()&&!qt.empty())
	{
		if(qs.size()<=qt.size())
		{
			auto [d,u,i]=qs.top();
			int v=gs[u][i].v;
			qs.pop();
			if(i+1<gs[u].size())
			{
				qs.push({ds[u]+gs[u][i+1].w,u,i+1});
			}
			if(vs[v])
			{
				continue;
			}
			vs[v]=1;
			ds[v]=d;
			us.push_back(v);
			if(vt[v])
			{
				z=v;
				break;
			}
			if(!gs[v].empty())
			{
				qs.push({d+gs[v][0].w,v,0});
			}
		}
		else
		{
			auto [d,u,i]=qt.top();
			int v=gt[u][i].v;
			qt.pop();
			if(i+1<gt[u].size())
			{
				qt.push({dt[u]+gt[u][i+1].w,u,i+1});
			}
			if(vt[v])
			{
				continue;
			}
			vt[v]=1;
			dt[v]=d;
			ut.push_back(v);
			if(vs[v])
			{
				z=v;
				break;
			}
			if(!gt[v].empty())
			{
				qt.push({d+gt[v][0].w,v,0});
			}
		}
	}
	if(!z)
	{
		for(auto u:us)
		{
			vs[u]=0;
		}
		for(auto u:ut)
		{
			vt[u]=0;
		}
		return -1;
	}
	ll res=ds[z]+dt[z];
	for(auto u:us)
	{
		ll lim=ds[z]-ds[u]<<1;
		for(auto e:gs[u])
		{
			if(e.w>=lim)
			{
				break;
			}
			if(vt[e.v])
			{
				res=min(res,ds[u]+e.w+dt[e.v]);
			}
		}
	}
	for(auto u:ut)
	{
		ll lim=dt[z]-dt[u]<<1;
		for(auto e:gt[u])
		{
			if(e.w>=lim)
			{
				break;
			}
			if(vs[e.v])
			{
				res=min(res,ds[e.v]+e.w+dt[u]);
			}
		}
	}
	for(auto u:us)
	{
		vs[u]=0;
	}
	for(auto u:ut)
	{
		vt[u]=0;
	}
	return res;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>q>>sd;
	mt19937 rnd(sd);
	auto ver=[&](){
		static const unsigned LIM=-1u/n*n;
		unsigned x;
		for(x=rnd();x>=LIM;x=rnd());
		return x%n+1;
	};
	for(int i=1;i<=m;i++)
	{
		int u=ver(),v=ver();
		unsigned 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;});
	}
	while(q--)
	{
		int s,t;
		cin>>s>>t;
		cout<<query(s,t)<<'\n';
	}
	cout<<flush;
	return 0;
}