#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define pb push_back
#define eb emplace_back
#define rz resize
#define MP make_pair
#define MT make_tuple
#define IT iterator
#define fi first
#define se second
#define For(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
#define Rep(i, a, b) for (int i = (int)(a); i >= (int)(b); --i)
#define CLR(a, v) memset(a, v, sizeof(a))
#define CPY(a, b) memcpy(a, b, sizeof(a))
#define debug cerr << "ztxakking\n"
#define y0 ztxaknoi
#define y1 ztxakioi
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using uint = unsigned int;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pli = pair<ll, int>;
using pil = pair<int, ll>;
using vi = vector<int>;
template<typename T>
using V = vector<T>;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
const int N = 2e5 + 7;
const ll Inf = 0x3fffffffffffffff;
int n, m, q;
uint seed;
V<pil> G0[N], G1[N];
V<tuple<int, int, ll>> generate_edges(int n, int m, uint seed) {
  mt19937 gen(seed);
  V<tuple<int, int, ll>> edges(m);
  uint mx = -1u / n * n;
  auto sample = [&] () {
    uint x;
    do { x = gen(); } while (x >= mx);
    return x % n + 1;
  };
  for(auto &[u, v, w] : edges) {
    u = sample();
    v = sample();
    w = gen();
  } // edge (u, v, w)
  return edges;
}
struct Info {
  int c, u;
  ll w;
  Info() = default;
  Info(int c, int u, ll w) : c(c), u(u), w(w) {}
  friend bool operator < (Info x, Info y) {
    return x.w > y.w;
  }
};
priority_queue<Info> qL, qR;
ll dL[N], dR[N];
bitset<N> visL, visR;
vi xL, xR;
ll dist(int s, int t) {
  if (s == t) return 0;
  int p = -1;
  dL[s] = dR[t] = 0, xL.pb(s), xR.pb(t), visL[s] = visR[t] = 1;
  while (qL.size()) qL.pop();
  while (qR.size()) qR.pop();
  if (G0[s].size()) qL.emplace(0, s, G0[s][0].se);
  if (G1[s].size()) qR.emplace(0, t, G1[t][0].se);
  for (int t = 0; qL.size() && qR.size(); t ^= 1) {
    if (t) {
      auto [c, u, w] = qL.top(); qL.pop();
      int v = G0[u][c].fi;
      if (c + 1 < G0[u].size()) qL.emplace(c + 1, u, w - G0[u][c].se + G0[u][c + 1].se);
      if (!visL[v]) {
        dL[v] = w, visL[v] = 1, xL.pb(v);
        if (visR[v]) {
          p = v; break;
        }
        if (G0[v].size()) qL.emplace(0, v, w + G0[v][0].se);
      }
    } else {
      auto [c, u, w] = qR.top(); qR.pop();
      int v = G1[u][c].fi;
      if (c + 1 < G1[u].size()) qR.emplace(c + 1, u, w - G1[u][c].se + G1[u][c + 1].se);
      if (!visR[v]) {
        dR[v] = w, visR[v] = 1, xR.pb(v);
        if (visL[v]) {
          p = v; break;
        }
        if (G1[v].size()) qR.emplace(0, v, w + G1[v][0].se);
      }
    }
  }
  if (p == -1) return -1;
  ll ans = dL[p] + dR[p];
  for (int i : xL) {
    for (auto [j, w] : G0[i]) {
      if (w > (dL[p] - dL[i]) * 2) break;
      ans = min(ans, dL[i] + w + dR[j]);
    }
  }
  for (int i : xR) {
    for (auto [j, w] : G1[i]) {
      if (w > (dR[p] - dR[i]) * 2) break;
      ans = min(ans, dR[i] + w + dL[j]);
    }
  }
  for (int i : xL) visL[i] = 0, dL[i] = Inf;
  for (int i : xR) visR[i] = 0, dR[i] = Inf;
  xL.clear(), xR.clear();
  return ans;
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> m >> q >> seed;
  V<tuple<int, int, ll>> edges = generate_edges(n, m, seed);
  for (auto [u, v, w] : edges) G0[u].eb(v, w), G1[v].eb(u, w);
  For(i, 1, n) {
    auto cmp = [&] (pil x, pil y) { return x.se < y.se; };
    sort(all(G0[i]), cmp), sort(all(G1[i]), cmp);
  }
  For(i, 1, n) dL[i] = dR[i] = Inf;
  visL.reset(), visR.reset();
  while (q--) {
    int s, t; cin >> s >> t;
    cout << dist(s, t) << '\n';
  }
  cerr << (double)(clock()) / CLOCKS_PER_SEC << '\n';
  return 0;
}