// Author: Klay Thompson
// Problem: C. 最短路径
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define per(i, j, k) for (int i = (j); i >= (k); --i)
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
using ll = long long;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;

template<class T>inline void chkmn(T &x, T y) { if (y < x) x = y; }
template<class T>inline void chkmx(T &x, T y) { if (y > x) x = y; }

using namespace std;

vector<tuple<int, int, ll>> generate_edges(int n, int m, unsigned seed) {
  mt19937 gen(seed);
  vector<tuple<int, int, ll>> edges(m);
  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;
}

const int maxn = 3000010;
const ll inf = 1e18;

int n, m, t, vis[maxn], cur[maxn], rcur[maxn], from[maxn], rfrom[maxn];
ll dis[maxn], rdis[maxn];
unsigned seed;
vector<pll> e[maxn], re[maxn];
priority_queue<pll, vector<pll>, greater<pll>> q, rq;

ll solve(int s, int t) {
  vector<int> vec, rvec;
  q.emplace(0, s), dis[s] = 0, vec.emplace_back(s);
  rq.emplace(0, t), rdis[t] = 0, rvec.emplace_back(t);
  int x = -1;
  while (!q.empty() || !rq.empty()) {
    if (!q.empty()) {
      auto [cd, u] = q.top();
      q.pop();
      if (dis[u] != cd) continue;
      vis[u] |= 1;
      if (vis[u] == 3) { x = u; break; }
      while (from[u] && cur[from[u]] < SZ(e[from[u]])) {
        auto [v, w] = e[from[u]][cur[from[u]]++];
        if (dis[from[u]] + w < dis[v]) {
          dis[v] = dis[from[u]] + w, vec.emplace_back(v);
          from[v] = from[u], q.emplace(dis[v], v);
          break;
        }
      }
      while (cur[u] < SZ(e[u])) {
        auto [v, w] = e[u][cur[u]++];
        if (dis[u] + w < dis[v]) {
          dis[v] = dis[u] + w, vec.emplace_back(v);
          from[v] = u, q.emplace(dis[v], v);
          break;
        }
      }
    }
    if (!rq.empty()) {
      auto [cd, u] = rq.top();
      rq.pop();
      if (rdis[u] != cd) continue;
      vis[u] |= 2;
      if (vis[u] == 3) { x = u; break; }
      while (rfrom[u] && rcur[rfrom[u]] < SZ(re[rfrom[u]])) {
        auto [v, w] = re[rfrom[u]][rcur[rfrom[u]]++];
        if (rdis[rfrom[u]] + w < rdis[v]) {
          rdis[v] = rdis[rfrom[u]] + w, rvec.emplace_back(v);
          rfrom[v] = rfrom[u], rq.emplace(dis[v], v);
          break;
        }
      }
      while (rcur[u] < SZ(re[u])) {
        auto [v, w] = re[u][rcur[u]++];
        if (rdis[u] + w < rdis[v]) {
          rdis[v] = rdis[u] + w, rvec.emplace_back(v);
          rfrom[v] = u, rq.emplace(rdis[v], v);
          break;
        }
      }
    }
  }
  ll ans = inf;
  if (x == -1) { ans = -1; goto cle; }
  ans = dis[x] + rdis[x];
  for (int u : vec) for (auto [v, w] : e[u]) chkmn(ans, dis[u] + rdis[v] + w);
  cle:;
  for (int x : vec) {
    vis[x] = from[x] = rfrom[x] = cur[x] = rcur[x] = 0;
    dis[x] = rdis[x] = inf;
  }
  for (int x : rvec) {
    vis[x] = from[x] = rfrom[x] = cur[x] = rcur[x] = 0;
    dis[x] = rdis[x] = inf;
  }
  while (!q.empty()) q.pop();
  while (!rq.empty()) rq.pop();
  return ans;
}

int main() {
  cin.tie(nullptr) -> ios::sync_with_stdio(false);
  cin >> n >> m >> t >> seed;
  auto edges = generate_edges(n, m, seed);
  for (auto [u, v, w] : edges) {
    e[u].emplace_back(v, w);
    re[v].emplace_back(u, w);
  }
  rep (i, 1, n) sort(ALL(e[i]), [&](pll x, pll y) { return x.se < y.se; });
  rep (i, 1, n) sort(ALL(re[i]), [&](pll x, pll y) { return x.se < y.se; });
  rep (i, 1, n) dis[i] = rdis[i] = inf;
  while (t--) {
    int s, t;
    cin >> s >> t;
    cout << solve(s, t) << '\n';
  }
}