#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using u64=unsigned long long;
//using lll=__int128_t;
using lf=long double;
using Pr=pair<ll,ll>;
#define F(i,l,r) for(ll i=l;i<=ll(r);++i)
#define G(i,r,l) for(ll i=r;i>=ll(l);--i)
#define ct const
#define il inline
#define pb push_back
#define fi first
#define se second
#define mkr make_pair
template<class T>
il void tomn(T&x,T ct&y){y<x?x=y,0:0;}
template<class T>
il void tomx(T&x,T ct&y){x<y?x=y,0:0;}
#define dbg(...) fprintf(stderr,__VA_ARGS__)
#define CUT dbg("===================\n")
ct lf EPS=1e-10L;
il int dcmp(lf x){return fabs(x)<=EPS?0:(x<0?-1:1);}
ct ll INF=4e18L;
//ct int INF=1.02e9;
//il void rd(int&x){scanf("%d",&x);}
//il void rd(ll&x){scanf("%lld",&x);}

ct ll P=1000000007;
void add2(ll&x,ll y){x+=y,x-=((-(x>=P))&P);}
void sub2(ll&x,ll y){x-=y,x+=((-(x<0))&P);}
ll add(ll x,ll y){return add2(x,y),x;}
ll sub(ll x,ll y){return sub2(x,y),x;}

ct int N=3050;
struct Ed{int v;ll w;};
vector<Ed>g[N];

void generate_edges(int n, int m, unsigned seed) {
	std::mt19937 gen(seed);
	unsigned max = -1u / n * n;
	auto sample = [&]() {
	    unsigned x;
	    do { x = gen(); } while(x >= max);
	    return x % n + 1;
	};
	F(i,1,m){
		auto u = sample();
		auto v = sample();
    	auto w = gen();
    	
//		cerr<<u<<" "<<v<<" "<<w<<endl;
    	
    	g[u].pb(Ed{(int)v,w});
	}
}

int n;
ll dis[N][N];
void dij(int s,ll*d){
	priority_queue<Pr>pq;
	F(i,1,n)d[i]=INF;
	pq.push(Pr(d[s]=0,s));
	while(!pq.empty()){
		Pr p=pq.top();pq.pop();
		int u=p.se;ll dis=p.fi;
		if(d[u]<dis)continue;
		for(Ed e:g[u])if(d[e.v]>dis+e.w)
			pq.push(Pr(d[e.v]=dis+e.w,e.v));
	}
}
int m,q;
int main(){
#ifdef LOCAL
	freopen("C.in","r",stdin);
	freopen("C.out","w",stdout);
#endif
	unsigned seed;
	scanf("%d%d%d%u",&n,&m,&q,&seed);
	generate_edges(n,m,seed);
	F(i,1,n)dij(i,dis[i]);
	F(i,1,q){
		int s,t;scanf("%d%d",&s,&t);
		ll ans=dis[s][t];
		printf("%lld\n",ans>=INF?-1:ans);
	}
}