#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long
#define sz(a) ((int) (a).size())
#define vi vector < int >
#define me(a, x) memset(a, x, sizeof(a))
#define ull unsigned long long
#define ld __float128
#define pb emplace_back
using namespace std;
const int N = 1 << 21;
struct edge {
	int u, v;
	ll w;
};
std::vector<edge> generate_edges(int n, int m, unsigned seed) {
    std::mt19937 gen(seed);
    std::vector<edge> edges(m);
    unsigned max = -1u / n * n;
    auto sample = [&]() {
        unsigned x;
        do { x = gen(); } while(x >= max);
        return x % n + 1;
    };
	for(auto&e : edges) {
		e.u = sample();
		e.v = sample();
		e.w = gen();
    } // u 到 v 存在边权为 w 的边
    return edges;
}
int n, m, q;
ll seed;
vector<pair<int,ll>>e[N], re[N];
ll dis[N];
int lst[N];
vi road[N];
ll lstw[N];
void dijkstra(int pos) {
	priority_queue<pair<ll,int>>pq;
	pq.push({0, pos});
	L(i, 1, n) dis[i] = 1e18;
	vi vis(n + 1);
	dis[pos] = 0;
	while(!pq.empty()) {
		auto u = pq.top().second;
		pq.pop();
		if(vis[u])continue;
		if(lst[u]) {
			road[u] = road[lst[u]], road[u].pb(u);
		}
		vis[u] = 1;
		for(auto&E : e[u]) {
			int to = E.first;
			if(dis[to] > dis[u] + E.second) {
				dis[to] = dis[u] + E.second;
				pq.push({-dis[to], to});
				lstw[to] = E.second;
				lst[to] = u;
			}
		}
	}
}
ll dis1[N], dis2[N];
int vis[N], que[N], all;
int use[N];
mt19937_64 rnd;
inline int rad(int l, int r) {
	return rnd() % (r - l + 1) + l;
}
int pick[N], seg1[N], seg2[N];
const int xN = 1 << 18;
void upd1(int x) {
	seg1[x + xN] = x;
	for(int u = (x + xN) >> 1; u; u >>= 1) {
		if(dis1[x] >= dis1[seg1[u]]) break;
		seg1[u] = x;
	}
}
void del1(int x) {
	seg1[x + xN] = 0;
	for(int u = (x + xN) >> 1; u; u >>= 1) 
		seg1[u] = dis1[seg1[u * 2]] < dis1[seg1[u * 2 + 1]] ? seg1[u * 2] : seg1[u * 2 + 1];
}

void upd2(int x) {
	seg2[x + xN] = x;
	for(int u = (x + xN) >> 1; u; u >>= 1) {
		if(dis2[x] >= dis2[seg2[u]]) break;
		seg2[u] = x;
	}
}
void del2(int x) {
	seg2[x + xN] = 0;
	for(int u = (x + xN) >> 1; u; u >>= 1) 
		seg2[u] = dis2[seg2[u * 2]] < dis2[seg2[u * 2 + 1]] ? seg2[u * 2] : seg2[u * 2 + 1];
}
int ban1[N], ban2[N];
const int M = 1 << 18;
int main() {
	ios :: sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	// n = 2e5, m = 3e6, q = 1000, seed = 114514;
	cin >> n >> m >> q >> seed;
	auto E = generate_edges(n, m, seed);
	sort(E.begin(), E.end(), [&] (edge a, edge b) {
		return a.w < b.w;
	});
	for(auto&ed : E) if(ed.u != ed.v) e[ed.u].pb(ed.v, ed.w), re[ed.v].pb(ed.u, ed.w);
	// dijkstra(1);
	// L(i, 1, n) {
	// 	dist[i] = dis[i];
	// }
	
	// L(s, 0, 100) E.erase(E.begin());
	// L(i, 1, n) e[i].clear();
	// for(auto&ed : E) e[ed.u].pb(ed.v, ed.w);
	// dijkstra(1);
	// int cnt = 0;
	// L(i, 1, n) {
	// 	if(dist[i] != dis[i]) {
	// 		++cnt;
	// 	}
	// }
	// cout << cnt << endl;

	L(i, 0, n) dis1[i] = dis2[i] = 1e18;
	while(q--) {
		int x, y;
		x = rad(1, n);
		y = rad(1, n);
		cin >> x >> y;
		if(x == y) {
			cout << 0 << '\n';
			continue;
		} 
		all = 2, que[1] = x, que[2] = y, vis[x] = vis[y] = 1;
		dis1[x] = 0, dis2[y] = 0;
		upd1(x), upd2(y);
		ll ans = 1e18;
		while(true) {
			if(min(dis1[seg1[1]], dis2[seg2[1]]) * 2 >= ans) {
				break;
			}
			if(dis1[seg1[1]] < dis2[seg2[1]]) {
				int u = seg1[1];
				del1(u);
				// cout << "u = " << u << ' ' << dis1[u] << endl;
				for(auto&E : e[u]) {
					int to = E.first;
					if(dis1[to] > dis1[u] + E.second) {
						dis1[to] = dis1[u] + E.second;
						if(!vis[to]) vis[to] = 1, que[++all] = to;
						else ans = min(ans, dis1[to] + dis2[to]);
						if(dis1[to] * 2 < ans) upd1(to);
					}
				}
			} else {
				int u = seg2[1];
				del2(u);
				for(auto&E : re[u]) {
					int to = E.first;
					if(dis2[to] > dis2[u] + E.second) {
						dis2[to] = dis2[u] + E.second;
						if(!vis[to]) vis[to] = 1, que[++all] = to;
						else ans = min(ans, dis1[to] + dis2[to]);
						if(dis2[to] * 2 < ans) upd2(to);
					}
				}
			}
		}
		L(i, 1, all) dis1[que[i]] = dis2[que[i]] = 1e18, vis[que[i]] = 0;
		if(ans > 1e17) cout << -1 << '\n';
		else cout << ans << '\n';
	}
	// L(i, 1, n) if(i % 10 == 0) cout << 1. * dis[i] / mx << ' ' << sz(road[i]) << endl;
	
	// L(i, 1, n) cout << sz(road[i]) << ' ';
	// cout << endl;
	return 0;
}