#include <bits/stdc++.h>
#define REP(i, first, last) for (int i = (first); i <= (last); ++i)
#define DOW(i, first, last) for (int i = (first); i >= (last); --i)
using namespace std;
#define tup tuple<int, int, int>
#define pb emplace_back
#define ull unsigned long long
const int N = 3e5 + 5, M = 2e5 + 5, Sg = 26;
const int mod1 = 1e9 + 9, mod2 = 998244353;
const long long inf = 0x3f3f3f3f3f3f3f3fll;
const int dx[] = {-1, -1, -1, 0, 0, 0, 1, 1, 1};
const int dy[] = {-1, 0, 1, -1, 0, 1, -1, 0, 1};
const int P = 1ll << 21, S = P - 1;
vector<tuple<int, int, long long>> generate_edges(int n, int m, unsigned seed) {
  mt19937 gen(seed);
  vector<tuple<int, int, long long>> 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();
  }  // u 到 v 存在边权为 w 的边
  return edges;
}
#define int long long
int n, m, q, seed;
vector<pair<int, int>> edge[3][N];
int dis[3][N];
int pos[3][N];
int vis[N];
int dist(int s, int t) {
  priority_queue<tup, vector<tup>, greater<tup>> q[2];
  q[0].emplace(0, 0, s), q[1].emplace(0, 0, t);
  dis[0][s] = dis[1][t] = 0;
  int k = 0;
  auto ins = [&](int x) {
    if (pos[k][x] == edge[k][x].size() || !x) return;
    auto [w, v] = edge[k][x][pos[k][x]++];
    dis[k][v] = min(dis[k][v], dis[k][x] + w);
    q[k].emplace(dis[k][v], x, v);
  };
  vector<int> del[2];
  int aim = 0;
  while (!q[0].empty() && !q[1].empty()) {
    auto [c, u, v] = q[k].top();
    q[k].pop(), ins(u);
    // cerr << u << '\n';
    if (vis[v] >> k & 1) continue;
    vis[v] |= 1 << k;
    del[k].pb(v);
    cerr << vis[v] << ' ' << k << '\n';
    if ((vis[v] & 1) && (vis[v] & 2)) {
      aim = v;
      break;
    }
    ins(v), k ^= 1;
  }
  int ans = -1;
  if (aim) {
    ans = dis[0][aim] + dis[1][aim];
    REP(k, 0, 1) for (int u : del[k]) for (auto [w, v] : edge[k][u]) {
      int nu = dis[k][u], nv = dis[k ^ 1][v];
      if (((vis[u] | vis[v]) & 1) && ((vis[u] | vis[v]) & 2))
        ans = min(ans, nu + nv + w);
    }
  }
  REP(k, 0, 1) {
    while (!q[k].empty()) {
      int v = get<2>(q[k].top());
      q[k].pop();
      pos[k][v] = vis[v] = 0, dis[k][v] = inf;
    }
    for (int v : del[k]) pos[k][v] = vis[v] = 0, dis[k][v] = inf;
  }
  return ans;
}
void Solve() {
  cin >> n >> m >> q >> seed;
  auto liste = generate_edges(n, m, seed);
  for (auto [u, v, w] : liste) edge[0][u].pb(w, v), edge[1][v].pb(w, u);
  REP(i, 1, n) REP(j, 0, 1) sort(edge[j][i].begin(), edge[j][i].end());
  memset(dis, 0x3f, sizeof dis);
  REP(i, 1, q) {
    int s, t;
    cin >> s >> t;
    cout << dist(s, t) << '\n';
  }
}
signed main() {
  //	freopen(".in", "r", stdin);
  //	freopen(".out", "w", stdout);
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);
  int T = 1;
  //	cin >> T;
  while (T--) {
    Solve();
  }
  return 0;
}