#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];
int ans;
vector<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<pii,vector<pii>,greater<> > ps,pt;
void dij(){
    for(int i:ap) dis[i][1]=dis[i][2]=0x3f3f3f3f3f3f3f3f,cl[i]=0;
    ap.clear();
    dis[s][1]=dis[t][2]=0;
    while(ps.size()) ps.pop();
    while(pt.size()) pt.pop();
    ps.emplace(0,s);
    pt.emplace(0,t);
    ap.push_back(s);
    ap.push_back(t);
    while(ps.size()){
        int x=ps.top().second;
        ps.pop();
        if(!cl[x]){
            cl[x]=1;
            for(pii i:e[x]){
                if(dis[i.first][1]>dis[x][1]+i.second){
                    ap.push_back(i.first);
                    dis[i.first][1]=dis[x][1]+i.second;
                    ps.emplace(dis[i.first][1],i.first);
                }
            }
        }else if(cl[x]==2) return o=x,void();
        x=pt.top().second;
        pt.pop();
        if(!cl[x]){
            ap.push_back(x);
            cl[x]=2;
            for(pii i:r[x]){
                if(dis[i.first][2]>dis[x][2]+i.second){
                    ap.push_back(i.first);
                    dis[i.first][2]=dis[x][2]+i.second;
                    pt.emplace(dis[i.first][2],i.first);
                }
            }
        }else if(cl[x]==1) return o=x,void();
    }
}

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<=(n==4?q:2);i++){
        cin>>s>>t;
        dij();
        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;
                    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;
}