#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <random>
#include <tuple>
#include <queue>
#define int long long
using namespace std;
const int inf = 0x7ffffffffffffff;
vector<pair<int, int> > gs[200005];
vector<pair<int, int> > gt[200005];
int n, m, q, seed;
struct node {
    int x, dis, cur;
};
bool operator<(node a, node b) { return a.dis > b.dis; }
int ds[200005], dt[200005];
int vs[200005], vt[200005];
vector<int> Ss, St;
priority_queue<node> qs, qt;
int Query(int s, int t) {
    if (s == t) 
        return 0;
    if (gs[s].empty() || gt[t].empty()) 
        return -1;
    int z = -1;
    ds[s] = dt[t] = 0;
    vs[s] = vt[t] = 1;
    Ss.emplace_back(s);
    St.emplace_back(t);
    qs.push((node) { s, gs[s][0].second, 0 });
    qt.push((node) { t, gt[t][0].second, 0 });
    while (!qs.empty() && !qt.empty()) {
        if (qs.size() <= qt.size()) {
            node tmp = qs.top();
            qs.pop();
            int x = tmp.x;
            for (int i = tmp.cur + 1; i < (int)gs[x].size(); i++) {
                if (!vs[gs[x][i].first]) {
                    qs.push((node) { x, ds[x] + gs[x][i].second, i });
                    break;
                }
            }
            int v = gs[x][tmp.cur].first;
            if (vs[v]) 
                continue;
            vs[v] = 1, ds[v] = tmp.dis;
            Ss.emplace_back(v);
            if (vt[v]) {
                z = v;
                break;
            }
            if (gs[v].size()) 
                qs.push((node) { v, ds[v] + gs[v][0].second, 0 });
        } else {
            node tmp = qt.top();
            qt.pop();
            int x = tmp.x;
            for (int i = tmp.cur + 1; i < (int)gt[x].size(); i++) {
                if (!vt[gt[x][i].first]) {
                    qt.push((node) { x, dt[x] + gt[x][i].second, i });
                    break;
                }
            }
            int v = gt[x][tmp.cur].first;
            if (vt[v]) 
                continue;
            vt[v] = 1, dt[v] = tmp.dis;
            St.emplace_back(v);
            if (vs[v]) {
                z = v;
                break;
            }
            if (gt[v].size()) 
                qt.push((node) { v, dt[v] + gt[v][0].second, 0 });
        }
    }
    if (z == -1) {
        for (auto v : Ss) vs[v] = 0;
        for (auto v : St) vt[v] = 0;
        Ss.clear(), St.clear();
        return -1;
    }
    int ans = ds[z] + dt[z];
    for (auto v : Ss) {
        int lim = (ds[z] - ds[v]) << 1;
        for (auto e : gs[v]) {
            if (e.second >= lim) 
                break;
            if (vt[e.first])
                ans = min(ans, ds[v] + dt[e.first] + e.second);
        }
    }
    for (auto v : St) {
        int lim = (dt[z] - dt[v]) << 1;
        for (auto e : gt[v]) {
            if (e.second >= lim) 
                break;
            if (vs[e.first])
                ans = min(ans, dt[v] + ds[e.first] + e.second);
        }
    }
    for (auto v : Ss) vs[v] = 0;
    for (auto v : St) vt[v] = 0;
    Ss.clear(), St.clear();
    return ans;
}
signed main() {
    cin >> n >> m >> q >> 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();
        gs[u].emplace_back(make_pair(v, w));
        gt[v].emplace_back(make_pair(u, w));
        // cout << u << " " << v << " " << w << " asdf\n";
    }
    for (int i = 1; i <= n; i++) {
        sort(gs[i].begin(), gs[i].end(), [](pair<int, int> a, pair<int, int> b) { return a.second < b.second; });
        sort(gt[i].begin(), gt[i].end(), [](pair<int, int> a, pair<int, int> b) { return a.second < b.second; });
    }
    while (q--) {
        int s, t;
        cin >> s >> t;
        cout << Query(s, t) << "\n";
    }
    return 0;
}