// Writer: Hridaya   Time:2024.9.12   By:NFLS
/********************************************/
// #pragma GCC optimize(3,"Ofast","inline")
// #include <iostream>       // cin, cout, cerr, getline
#include <bits/stdc++.h>
// #include <utility>        // pair, make_pair, swap, move
// #include <ctime>          // clock, time, difftime, tm, localtime
// #include <unordered_map>  // unordered_map, unordered_multimap
// #include <unordered_set>  // unordered_set, unordered_multiset
// #include <algorithm>      // sort, find, reverse, binary_search, max_element, min_element
// #include <ios>            // ios_base, ios_base::failure, ios::sync_with_stdio
// #include <vector>         // vector, vector::push_back, vector::size, vector::at
// #include <bitset>         // bitset, bitset::set, bitset::reset
// #include <cstring>        // memset, memcpy, strcmp, strlen
// #include <map>            // map, multimap, map::insert
// #include <set>            // set, multiset, set::insert
// #include <queue>          // queue, priority_queue
// #include <stack>          // stack, stack::push, stack::pop
// #include <deque>          // deque, deque::push_back, deque::pop_front
// #include <list>           // list, list::push_back, list::remove
// #include <cmath>          // sqrt, pow, sin, cos, log
// #include <cstddef>        // size_t, ptrdiff_t
// #include <cstdll>        // ll8_t, ll16_t, ll32_t, ll64_t, ull8_t, ull16_t, ull32_t, ull64_t
// #include <climits>        // INT_MAX, CHAR_MIN
// #include <iterator>       // iterator, advance, next, prev
// #include <chrono>         // chrono::steady_clock, chrono::system_clock, chrono::duration
// #include <fstream>        // ifstream, ofstream, fstream
using namespace std;
typedef long long ll;
#define foru(i,x,y) for (register ll i(x); i <= y; ++i)
#define ford(i,x,y) for (register ll i(x); i >= y; --i)
#define Linf 9223372036854775807
#define Iinf 2147483647
#define Sinf 32767
namespace IO {
	char ch ('~');
	template<typename Type>
	inline Type read() {
		Type x(0);
		bool m(0);
		while (!isdigit(ch)) {
			m |= (ch == '-');
			ch = getchar(); }
		while (isdigit(ch)) {
			x = (x << 1) + (x << 3) + (ch ^ 48);
			ch = getchar(); }
		return m ? (~x + 1) : x; }
	template<typename Type>
	inline void write(Type x) {
		if (x < 0) putchar('-'), x = (~x + 1);
		if (x > 9) write(x / 10);
		putchar(x % 10 ^ 48); }
	template<typename Type>
	inline void writes(Type x, char c) {
		write(x), putchar(c); }
#define read() read<ll>()
#define Jianghu_bloke \
	freopen("QwQ.in", "r", stdin); freopen("QwQ.out", "w", stdout);
} using namespace IO;
#define pb emplace_back
#define fi first
#define se second
const int N (5e6 + 10);
struct edge {
	ll u, v;
	ll w; };
std::vector<edge> generate_edges(ll n, ll 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(); }
	return edges; }
ll n, m, q;
ll seed;
vector<pair<ll, ll>>e[N], re[N];
ll dis[N];
ll lst[N];
std :: vector<ll> road[N];
ll lstw[N];
inline void dijkstra(ll pos) {
	priority_queue<pair<ll, ll>>pq;
	pq.push({0, pos });
	foru(i, 1, n) dis[i] = 1e18;
	vector<ll> vis(n + 1);
	dis[pos] = 0;
	while (!pq.empty()) {
		auto u = pq.top().se; 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]) {
			ll to (E.fi);
			if (dis[to] > dis[u] + E.se) {
				dis[to] = dis[u] + E.se;
				pq.push({-dis[to], to });
				lstw[to] = E.se;
				lst[to] = u; } } } }
ll dis1[N], dis2[N];
ll vis[N], que[N], all, seg1[N], seg2[N], use[N];
mt19937_64 rnd;
inline ll rad(ll l, ll r) {
	return rnd() % (r - l + 1) + l; }
const ll xN = 1 << 18;
inline void upd1(ll x) {
	seg1[x + xN] = x;
	for (ll u = (x + xN) >> 1; u; u >>= 1) {
		if (dis1[x] > dis1[seg1[u]]) break;
		seg1[u] = x; } }
inline void del1(ll x) {
	seg1[x + xN] = 0;
	for (ll 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]; }
inline void upd2(ll x) {
	seg2[x + xN] = x;
	for (ll u = (x + xN) >> 1; u; u >>= 1) {
		if (dis2[x] > dis2[seg2[u]]) break;
		seg2[u] = x; } }
inline void del2(ll x) {
	seg2[x + xN] = 0;
	for (ll 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]; }
ll ban1[N], ban2[N];
const ll M = 1 << 18;
namespace Hridaya {
	inline void solve() {
		ll x (read()), y(read());
		if (x == y) return puts("0"), void();
		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 (1) {
			if (ans == 1e17 && (dis1[seg1[1]] > 1e17 || dis2[seg2[1]] > 1e17)) break;
			if (min(dis1[seg1[1]], dis2[seg2[1]]) * 2 >= ans) break;
			if (dis1[seg1[1]] < dis2[seg2[1]]) {
				ll u = seg1[1];
				del1(u);
				for (auto&E : e[u]) {
					ll to = E.fi;
					if (dis1[to] > dis1[u] + E.se) {
						dis1[to] = dis1[u] + E.se;
						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 {
				ll u = seg2[1];
				del2(u);
				for (auto&E : re[u]) {
					ll to = E.fi;
					if (dis2[to] > dis2[u] + E.se) {
						dis2[to] = dis2[u] + E.se;
						if (!vis[to]) vis[to] = 1, que[++all] = to;
						else ans = min(ans, dis1[to] + dis2[to]);
						if (dis2[to] * 2 < ans) upd2(to); } } } }
		foru(i, 1, all) dis1[que[i]] = dis2[que[i]] = 1e18, vis[que[i]] = 0;
		writes(ans > 1e17 ? -1 : ans, '\n'); }
	signed main() {
		n = read(), m = read(), q = read(), seed = read<ll>();
		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);
		foru(i, 0, n) dis1[i] = dis2[i] = 1e18;
		while (q--) solve();
		return 0; }
//	Main Space
}
signed main() {
//	Jianghu_bloke
	Hridaya :: main();
//	Coding Completed!
	return 0; }