#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 1e18
#define fr(i,l,r) for (i=(l); i<=(r); i++)
#define rfr(i,l,r) for (i=(l); i>=(r); i--)
template<typename T>inline void read(T &n){
    T w=1; n=0; char ch=getchar();
    while (!isdigit(ch) && ch!=EOF){ if (ch=='-') w=-1; ch=getchar(); }
    while (isdigit(ch) && ch!=EOF){ n=(n<<3)+(n<<1)+(ch&15); ch=getchar(); }
    n*=w;
}
template<typename T>inline void write(T x){
    if (x==0){ putchar('0'); return ; }
    T tmp;
    if (x>0) tmp=x;
    else tmp=-x;
    if (x<0) putchar('-');
    char F[105];
    long long cnt=0;
    while (tmp){
        F[++cnt]=tmp%10+48;
        tmp/=10;
    }
    while (cnt) putchar(F[cnt--]);
}
#define Min(x,y) x = min(x,y)
#define Max(x,y) x = max(x,y)
//基础配置=================================================================================
const ll N = 200005, M = 3000005;
ll n,m,qt,seed;
struct edge{
    ll y,v;
    edge(ll _y=0,ll _v=0){
        y = _y; v = _v;
    }
    bool operator < (const edge o)const{
        return v<o.v;
    }
};
vector<edge> e[2][N];//0反边，1正边
void generate_edges(int n, int m, unsigned seed) {
    std::mt19937 gen(seed);
    std::vector<std::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();
        // printf("%lld %lld %lld\n",u,v,w);
        e[1][u].push_back(edge(v,w));
        e[0][v].push_back(edge(u,w));
    } // u 到 v 存在边权为 w 的边
    // return edges;
}
struct node{
    ll x,v,op,ft,nw;
    node(ll _x=0,ll _v=0,ll _op=0,ll _ft=0,ll _nw=0){
        x = _x; v = _v; op = _op; ft = _ft; nw = _nw;
    }
    bool operator < (const node o)const{
        return v>o.v;
    }
};
priority_queue<node> q;
ll top,stk[N+N];
ll ss,cl[N+N];
ll f[N][2];
void insert(ll x,ll op,ll nw){
    for (ll i=nw; i<e[op][x].size(); i++){
        ll go = e[op][x][i].y;
        if (f[x][op]+e[op][x][i].v<f[go][op]){
            if (f[go][0]>=inf && f[go][1]>=inf) cl[++ss] = go;
            f[go][op] = f[x][op]+e[op][x][i].v;
            // printf("insert f[%lld][%lld] = %lld\n",go,op,f[go][op]);
            q.push(node(go,f[go][op],op,x,i+1));
            break;
        }
    }
}
ll solve(ll x,ll y){
    if (x==y) return 0;
    ll i,j;
    ss = top = 0;
    f[x][1] = f[y][0] = 0; cl[++ss] = x; cl[++ss] = y;
    while (!q.empty()) q.pop();
    q.push(node(x,0,1,-1,inf));
    q.push(node(y,0,0,-1,inf));
    ll pos = -1;
    while (!q.empty()){
        node p = q.top(); q.pop();
        if (p.ft>0) insert(p.ft,p.op,p.nw);
        if (p.v>f[p.x][p.op]) continue;
        ll x = p.x, op = p.op;
        // printf("f[%lld][%lld] = %lld\n",x,op,f[x][op]);
        stk[++top] = x;
        if (f[x][0]<inf && f[x][1]<inf && pos==-1){ pos = x; break; }
        // if (p.ft>0) insert(p.ft,op,p.nw);
        insert(x,op,0);
    }
    if (pos==-1){
        fr(i,1,ss){
            ll x = cl[i];
            f[x][0] = f[x][1] = inf;
        }
        return -1;
    }
    ll ans = f[pos][1]+f[pos][0];
    fr(i,1,top){
        ll x = stk[i], lim;
        lim = 2*(f[pos][1]-f[x][1]);
        for (j=0; j<e[1][x].size(); j++){
            ll go = e[1][x][j].y, v = e[1][x][j].v;
            // if (v>lim) break;
            // if (f[x][1]+v+f[go][0]<=ans){
                // ans = f[x][1]+v+f[go][0];
                // printf("ans = %lld , lim = %lld , v = %lld\n",ans,lim,v);
            // }
            Min(ans,f[x][1]+v+f[go][0]);
        }
        lim = 2*(f[pos][0]-f[x][0]);
        for (j=0; j<e[0][x].size(); j++){
            ll go = e[0][x][j].y, v = e[0][x][j].v;
            // if (v>lim) break;
            // if (f[x][0]+v+f[go][1]<=ans){
                // ans = f[x][0]+v+f[go][1];
                // printf("ans = %lld , lim = %lld , v = %lld\n",ans,lim,v);
            // }
            Min(ans,f[x][0]+v+f[go][1]);
        }
    }
    fr(i,1,ss){
        ll x = cl[i];
        f[x][0] = f[x][1] = inf;
    }
    return ans;
}
int main(){
	// freopen("a.in","r",stdin);
//	freopen(".out","w",stdout);
    ll i,j;
    read(n); read(m); read(qt); read(seed);
    if (m>2000) return 0;
    generate_edges(n,m,seed);
    fr(i,1,n){
        if (e[1][i].size()==0) continue;
        sort(e[0][i].begin(),e[0][i].end());
        sort(e[1][i].begin(),e[1][i].end());
    }
    fr(i,1,n) f[i][0] = f[i][1] = inf;
    while (qt--){
        ll x,y;
        read(x); read(y);
       ll ans = solve(x,y);
       printf("%lld\n",ans);
    }
    return 0;
}
//g++ a.cpp -o a -Wall -Wl,--stack=512000000 -std=c++11 -O2