#include<bits/stdc++.h>
using namespace std;

#define int long long
// #define int128 __int128_t
#define ls p<<1
#define rs p<<1|1
#define msp(_array) memset(_array,0x3f,sizeof _array)
#define ms0(_array) memset(_array,0,sizeof _array)
#define msn(_array) memset(_array,-1,sizeof _array)
#define mc(_tar,_array) memcpy(_tar,_array,sizeof _tar)
#define pii pair<int,int>
#define endl '\n'

bool bg_memory;
const int mod=(1ll<<60)-1;
const int inf=1e18;
const int bs=23333;
const double eps=1e-6;
const int N=2e5+7,M=3e6+7;
inline void cmax(int &a,int b){a=a<b?b:a;}
inline void cmin(int &a,int b){a=a>b?b:a;}

int n,m,q,seed;
int s,t,o;
vector<pii> e[N],r[N];
int dis[N][3],cl[N][3];
int ans;
set<int> ap;
void generate_edges(){
    std::mt19937 gen(seed);
    unsigned max = -1u / n * n;
    auto sample = [&]() {
        unsigned x;
        do { x = gen(); } while(x >= max);
        return x % n + 1;
    };
    for(int i=1;i<=m;i++){
        int u=sample();
        int v=sample();
        int w=gen();
        e[u].push_back({v,w});
        r[v].push_back({u,w});
    }
}
priority_queue<pair<pii,int> > ps,pt;
void dij(){
    for(int i:ap) cl[i][1]=cl[i][2]=0;
    ap.clear();
    dis[s][1]=dis[t][2]=0;
    cl[s][1]=cl[t][2]=1;
    while(ps.size()) ps.pop();
    while(pt.size()) pt.pop();
    ps.push({{-e[s][0].second,s},0});
    pt.push({{-r[t][0].second,t},0});
    ap.insert(s);
    ap.insert(t);
    while(ps.size()&&pt.size()){
        pair<pii,int> x;
        if(ps.size()<=pt.size()){
            x=ps.top();
            x.first.first=-x.first.first;
            ps.pop();
            for(int j=x.second+1;j<e[x.first.second].size();j++){
                pii i=e[x.first.second][j];
                if(!cl[i.first][1]){
                    ps.push({{-dis[x.first.second][1]-i.second,x.first.second},j});
                    break;
                }
            }
            int v=e[x.first.second][x.second].first;
            if(cl[v][1]) continue;
            cl[v][1]=1;
            dis[v][1]=x.first.first;
            ap.insert(v);
            if(cl[v][2]) return o=v,void();
            if(e[v].size()) ps.push({{-dis[v][1]-e[v][0].second,v},0});
        }else{
            x=pt.top();
            x.first.first=-x.first.first;
            pt.pop();
            for(int j=x.second+1;j<r[x.first.second].size();j++){
                pii i=r[x.first.second][j];
                if(!cl[i.first][2]){
                    pt.push({{-dis[x.first.second][2]-i.second,x.first.second},j});
                    break;
                }
            }
            int v=r[x.first.second][x.second].first;
            if(cl[v][2]) continue;
            cl[v][2]=1;
            dis[v][2]=x.first.first;
            ap.insert(v);
            if(cl[v][1]) return o=v,void();
            if(r[v].size()) pt.push({{-dis[v][2]-r[v][0].second,v},0});
        }
    }
}

mt19937 rnd(time(0));
int Case=1;
void Main(){
    
    cin>>n>>m>>q>>seed;
    generate_edges();
    for(int i=1;i<=n;i++) sort(e[i].begin(),e[i].end(),[](pii a,pii b){return a.second<b.second;});
    for(int i=1;i<=n;i++) sort(r[i].begin(),r[i].end(),[](pii a,pii b){return a.second<b.second;});
    msp(dis);
    for(int i=1;i<=q;i++){
        cin>>s>>t;
        if(s==t){
            cout<<0<<endl;
            continue;
        }
        if(e[s].empty()||r[t].empty()){
            cout<<-1<<endl;
            continue;
        }
        o=0;
        dij();
        if(!o){
            cout<<-1<<endl;
            continue;
        }
        ans=dis[o][1]+dis[o][2];
        for(int j:ap){
            if(cl[j][1]){
                for(pii k:e[j]){
                    if(k.second>=2*(dis[o][1]-dis[j][1])) break;
                    if(cl[k.first][2]) cmin(ans,dis[j][1]+dis[k.first][2]+k.second);
                }
            }
        }
        cout<<ans<<endl;
    }

    return;
}
string RdFile="c";
bool en_memory;

signed main(){
    auto bg_clock=chrono::high_resolution_clock::now();
#ifdef ONLINE_JUDGE
    // freopen((RdFile+".in").c_str(),"r",stdin);
    // freopen((RdFile+".out").c_str(),"w",stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // cin>>Case;
    while(Case--) Main();
    auto en_clock=chrono::high_resolution_clock::now();
    auto duration_clock=chrono::duration_cast<chrono::microseconds>(en_clock-bg_clock);
#ifndef ONLINE_JUDGE
    cerr<<endl<<"code_time_used: "<<duration_clock.count()*0.001<<"ms"<<endl;
    cerr<<"code_memory_used: "<<(&en_memory-&bg_memory)/1024.0/1024<<"MB"<<endl;
#endif
    return 0;
}