#include <bits/stdc++.h>
using ll = long long;
const int N = 2e5 + 10;

int main() {
  std::cin.tie(0)->sync_with_stdio(0);
  int n, m, q, seed;
  std::vector<std::vector<std::pair<int, ll>>> g[2];
  std::cin >> n >> m >> q >> seed;
  g[0].resize(n + 1), g[1].resize(n + 1);
  std::mt19937 gen(seed);
  unsigned max = -1u / n * n;
  auto sample = [&]() {
    unsigned x;
    do {
      x = gen();
    } while (x >= max);
    return x % n + 1;
  };
  while (m--) {
    int u = sample(), v = sample();
    ll w = gen();
    if (u == v) continue;
    g[0][u].emplace_back(v, w), g[1][v].emplace_back(u, w);
    // std::cerr << u << ' ' << v << ' ' << w << '\n';
  }
  for (int i = 1; i <= n; i++) {
    for (int t : {0, 1})
      std::sort(g[t][i].begin(), g[t][i].end(),
                [&](auto a, auto b) { return a.second < b.second; });
  }
  static bool vis[2][N];
  static ll dis[2][N];
  int x = -1;
  while (q--) {
    int s, t;
    std::cin >> s >> t;
    if (s == t) {
      std::cout << 0 << '\n';
      continue;
    }
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    std::priority_queue<std::tuple<ll, int, std::vector<std::pair<int, ll>>::iterator>> pq[2];
    dis[0][s] = 0, dis[1][t] = 0;
    if (g[0][s].size()) pq[0].emplace(g[0][s].begin()->second, s, g[0][s].begin()), vis[0][s] = 1;
    if (g[1][t].size()) pq[1].emplace(g[1][t].begin()->second, t, g[1][t].begin()), vis[1][t] = 1;
    for (int c = 0; pq[0].size() && pq[1].size(); c ^= 1) {
      auto [d, u, it] = pq[c].top();
      auto [v, w] = *it;
      pq[c].pop();
      if (std::next(it) != g[c][u].end()) pq[c].emplace(dis[c][u] + std::next(it)->second, u, std::next(it));
      if (vis[c][v]) continue;
      // std::cerr << c << ' ' << v<< ' ' << d << '\n';
      dis[c][v] = d, vis[c][v] = 1;
      if (vis[c ^ 1][v]) {
        x = v;
        break;
      }
      if (g[c][v].size()) pq[c].emplace(d + g[c][v].begin()->second, v, g[c][v].begin());
    }
    if (x == -1) {
      std::cout << -1 << '\n';
      continue;
    }
    ll ans = dis[0][x] + dis[1][x];
    for (int u = 1; u <= n; u++)
      if (vis[0][u])
        for (auto [v, w] : g[0][u])
          if (vis[1][v]) ans = std::min(ans, dis[0][u] + w + dis[1][v]);
    std::cout << ans << '\n';
  }
}
/*
4 8 1 1112792816
2 3
*/