#include<bits/stdc++.h>
std::vector<std::tuple<int, int, long long>> generate_edges(int n, int m, unsigned seed) {
	std::mt19937 gen(seed);
	std::vector<std::tuple<int, int, long long>> edges(m);
	std::uniform_int_distribution<unsigned> vertex(1, n);
	unsigned max = -1u / n * n;
	auto sample = [&]() {
		unsigned x;
		do { x = gen(); } while(x >= max);
		return x % n + 1;
	};
	for(auto & [u, v, w] : edges) {
		u = sample();
		v = sample();
		w = gen();
	}
	return edges;
}
 
using std::cin, std::cout;
using ll = long long;
const int N = 200005;
const ll inf = 1e18;
using pr = std::pair<ll, int>;
 
int n, m, q; unsigned seed;
 
std::vector<pr> e[N], re[N];
 
int qc;
 
int vl[N], vr[N];
ll dl[N], dr[N];
 
struct edge {
	ll dist;
	std::vector<pr> * edges;
	int index;
	edge(ll dist, std::vector<pr> & edges, int index) : 
		dist(dist + edges[index].first), edges(&edges), index(index) {
		}
 
	int dest() const {
		return (*edges)[index].second;
	}
	std::optional<edge> next() const {
		if(index + 1 < (int) edges -> size()) {
			return edge(dist - (*edges)[index].first, *edges, index + 1);
		} else {
			return std::nullopt;
		}
	}
	bool operator < (const edge & y) const {
		return dist > y.dist;
	}
};
ll heap_op;
ll dist(int s, int t) {
	++ qc;
	if(s == t) {
		return 0;
	}
	e[0] = {pr(0, s)};
	re[0] = {pr(0, t)};
	std::priority_queue<edge> qL, qR;
	qL.emplace(0, e[0], 0), qR.emplace(0, re[0], 0);
	int p = -1;
	int cl = 0, cr = 0;
	std::vector<int> sL, sR;
	for(;qL.size() && qR.size();) {
		++ heap_op;
		if(cl < cr) {
			edge t = qL.top(); qL.pop();
			if(auto next = t.next()) qL.push(next.value());
			int x = t.dest();
			if(vl[x] == qc) continue;
			vl[x] = qc, dl[x] = t.dist, sL.push_back(x), ++ cl;
			if(vr[x] == qc) {
				p = x;
				break;
			}
			if(e[x].size()) qL.emplace(dl[x], e[x], 0);
		} else {
			edge t = qR.top(); qR.pop();
			if(auto next = t.next()) qR.push(next.value());
			int x = t.dest();
			if(vr[x] == qc) continue;
			vr[x] = qc, dr[x] = t.dist, sR.push_back(x), ++ cr;
			if(vl[x] == qc) {
				p = x;
				break;
			}
			if(re[x].size()) qR.emplace(dr[x], re[x], 0);
		}
	}
	if(p == -1) {
		return p;
	}
	ll ans = dl[p] + dr[p];
	for(int x : sL) {
		ll lim = 2 * (dl[p] - dl[x]);
		for(auto [v, p] : e[x]) {
			if(v >= lim) break;
			if(vr[p] == qc) ans = std::min(ans, dl[x] + v + dr[p]);
		}
	}
	for(int x : sR) {
		ll lim = 2 * (dr[p] - dr[x]);
		for(auto [v, p] : re[x]) {
			if(v >= lim) break;
			if(vl[p] == qc) ans = std::min(ans, dr[x] + v + dl[p]);
		}
	}
	return ans;
}
int main() {
//	freopen("in.txt", "r", stdin);
	std::ios::sync_with_stdio(false), cin.tie(0);
	cin >> n >> m >> q >> seed;
	puts("11111111");
	return 0;
	auto edges = generate_edges(n, m, seed);
	for(auto [u, v, w] : edges) {
		e[u].emplace_back(w, v);
		re[v].emplace_back(w, u);
	}
	std::cerr << "gen edges done " << double(clock()) / CLOCKS_PER_SEC << '\n';
	for(int i = 1;i <= n;++i) {
		sort(e[i].begin(), e[i].end());
		sort(re[i].begin(), re[i].end());
	}
	std::cerr << "sort edges done " << double(clock()) / CLOCKS_PER_SEC << '\n';
	for(int i = 0;i < q;++i) {
		int s, t;
		cin >> s >> t;
		cout << dist(s, t) << '\n';
		if(i % 10000 == 0) {
			std::cerr << "std " << i << '\n';
		}
	}
	std::cerr << "all done " << double(clock()) / CLOCKS_PER_SEC << '\n';
	std::cerr << "heap op_stat : " << double(heap_op) / q << '\n';
}

answer.code: In function ‘std::vector<std::tuple<int, int, long long int> > generate_edges(int, int, unsigned int)’:
answer.code:12:20: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   12 |         for(auto & [u, v, w] : edges) {
      |                    ^
answer.code: At global scope:
answer.code:20:15: warning: comma-separated list in using-declaration only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   20 | using std::cin, std::cout;
      |               ^
answer.code:46:14: error: ‘optional’ in namespace ‘std’ does not name a template type
   46 |         std::optional<edge> next() const {
      |              ^~~~~~~~
answer.code:46:9: note: ‘std::optional’ is only available from C++17 onwards
   46 |         std::optional<edge> next() const {
      |         ^~~
answer.code: In function ‘ll dist(int, int)’:
answer.code:74:42: error: ‘struct edge’ has no member named ‘next’
   74 |                         if(auto next = t.next()) qL.push(next.value());
      |                                          ^~~~
answer.code:85:42: error: ‘struct edge’ has no member named ‘next’
   85 |                         if(auto next = t.next()) qR.push(next.value());
      |                                          ^~~~
answer.code:102:26: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
  102 |                 for(auto [v, p] : e[x]) {
      |                          ^
answer.code:109:26: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
  109 |                 for(auto [v, p] : re[x]) {
      |                          ^
answer.code: In function ‘int main()’:
answer.code:123:18: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
  123 |         for(auto [u, v, w] : edges) {
      |                  ^