#if defined(_USE_PCH_)
#include "pch.hpp"
#else
#include <bits/stdc++.h>
#endif
#define RNG(V_, A_, B_, ...) for(int V_=(A_), V_##_END=(B_) __VA_OPT__(,) __VA_ARGS__; V_<=V_##_END; V_++)
#define IRNG(V_, A_, B_) for(int V_=(A_), V_##_END=(B_); V_>=V_##_END; V_--)
#ifdef _WIN32
#define long __int64
#endif
using namespace std;
const int MAXN=2e5+10,INF=1e9; const long INFLL=0x3f3f3f3f3f3f3f3f;
int n,m,qn,seed;
vector<pair<int,long>> G[2][MAXN];
long dis[2][MAXN],vis[2][MAXN]; vector<int> vec[2];
priority_queue<tuple<long,int,int>,vector<tuple<long,int,int>>,greater<tuple<long,int,int>>> pq[2];
long solve(int st,int ed){
    RNG(t,0,1){
        for(auto u:vec[t]) dis[t][u]=INFLL,vis[t][u]=0;
        vec[t].clear(); pq[t]={};
    }
    pq[0].push({0,st,-1}),pq[1].push({0,ed,-1});
    int meet=0;
    auto step=[&meet](int t){
        auto [d,fa,i]=pq[t].top(); pq[t].pop();
        int u=i<0?fa:G[t][fa][i].first;
        vec[t].push_back(u);
        if(i>=0&&i+1<(int)G[t][fa].size()){
            i++;
            pq[t].push({dis[t][fa]+G[t][fa][i].second,fa,i});
        }
        if(dis[t][u]>d){
            dis[t][u]=d;
            assert(!vis[t][u]),vis[t][u]=1;
            if(vis[!t][u]) meet=u;
            if(G[t][u].size()) pq[t].push({dis[t][u]+G[t][u].front().second,u,0});
        }
    };
    while(pq[0].size()||pq[1].size()){
        if(pq[0].size()) step(0);
        if(pq[1].size()) step(1);
        if(meet){
            long ret=dis[0][meet]+dis[1][meet];
            int t=vec[0].size()<vec[1].size()?0:1;
            auto& vc=vec[t];
            for(auto u:vc){
                for(auto [v,w]:G[t][u]) ret=min(ret,dis[t][u]+dis[!t][v]+w);
            }
            return ret;
        }
    }
    return -1;
}
int main(){
#if defined(_LOCAL_)
    freopen("in","r",stdin);
//  freopen("out","w",stdout);
#else
//  freopen("c.in","r",stdin);
//  freopen("c.out","w",stdout);
#endif
    ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    cin>>n>>m>>qn>>seed;
    {
        mt19937 rng(seed);
        uint64_t mx = -1u / n * n;
        auto sample = [&]()->int {
            uint64_t x;
            do { x = rng(); } while(x >= mx);
            return x % n + 1;
        };
        RNG(_,1,m){
            int u=sample(),v=sample(); long w=rng();
            G[0][u].push_back({v,w}),G[1][v].push_back({u,w});
        }
        RNG(t,0,1){
            RNG(i,1,n) sort(G[t][i].begin(),G[t][i].end(),[](auto x,auto y){ return x.second<y.second; });
        }
    }
    memset(dis,0x3f,sizeof(dis));
    RNG(_,1,qn){
        int s,t; cin>>s>>t;
        cout<<solve(s,t)<<"\n";
    }
}