//P4768
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <cmath>

#define LL long long
#define Cl(X,Y) memset((X),(Y),sizeof(X))
#define FOR(i,A,B) for(int i=A;i<=B;i++)
#define BOR(i,A,B) for(int i=A;i>=B;i--)
#define Lowbit(X) (X & (-X))
#define Skip cout<<endl;
#define INF 0x3f3f3f3f
#define Rson (X<<1|1)
#define Lson (X<<1)
using namespace std;
const int MaxN=4e5+10,MaxM=8e5+10;

int Total,Side,Task,Test,K,S,Limit;
bool Jud[MaxN];
int Next[MaxN<<1],Head[MaxN],End[MaxN<<1],Cur,Val[MaxN],Dist[MaxN],Tot;
int Last,Dep[MaxN],Anc[MaxN][21],Fa[MaxN<<1];
int NNext[MaxM<<1],HHead[MaxM],EEnd[MaxM<<1],CCur;
struct Edge{ int u,v,w1,w2; }E[MaxN<<1];
int Min[MaxM<<1];
struct Str { 
	int ID,V; 
	friend bool operator < (Str A,Str B) 
    { return A.V>B.V; }
};
priority_queue<Str>Mine;

inline void File() {
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
}

inline void Dijkstra() {
    Cl(Jud,false);
    Cl(Dist,0x3f);
    Dist[1]=0;
    while(!Mine.empty()) Mine.pop();
    Mine.push(Str{ 1,0 });
    while(!Mine.empty()) {
        Str New=Mine.top();
        Mine.pop();
        if(Jud[New.ID]) continue;
        Jud[New.ID]=true;
        for(int i=Head[New.ID];i;i=Next[i]) {
            if(Dist[End[i]]>New.V+Val[i]) {
                Dist[End[i]]=New.V+Val[i];
                if(!Jud[End[i]]) { Mine.push(Str{ End[i],Dist[End[i]] }); }
            }
        }
    }
    FOR(i,1,Total) Min[i]=Dist[i];
}

inline void Add_Edge_two(int From,int To) {
    NNext[++CCur]=HHead[From];
    HHead[From]=CCur;
    EEnd[CCur]=To;
}

inline void Add_Edge_one(int From,int To,int Temp) {
    Next[++Cur]=Head[From];
    Head[From]=Cur;
    End[Cur]=To;
    Val[Cur]=Temp;
}

int Res[MaxN<<1];

inline void DFS(int New,int Pre) {
    Dep[New]=Dep[Pre]+1;
    FOR(i,1,20) Anc[New][i]=Anc[Anc[New][i-1]][i-1];
    for(int i=HHead[New];i;i=NNext[i]) {
        if(EEnd[i]==Pre) continue;
        Anc[EEnd[i]][0]=New;
        DFS(EEnd[i],New);
        Min[New]=min(Min[New],Min[EEnd[i]]);
    }
}

inline int Get(int X,int Y) {
    BOR(i,20,0) if(Dep[X]>(1<<i) && Res[Anc[X][i]]>Y) X=Anc[X][i];
    return Min[X];
}

inline int Find_Fa(int New) {
    if(New==Fa[New]) return New;
    else return Fa[New]=Find_Fa(Fa[New]);
}

inline bool Comp(Edge A,Edge B) { return A.w2>B.w2; }
inline void Kruskal() {
    int Dot=Total,Group=0;
    FOR(i,1,(Total<<1)) Fa[i]=i;
    sort(E+1,E+Side+1,Comp);
    FOR(i,1,Side) {
        int A=Find_Fa(E[i].u),B=Find_Fa(E[i].v);
        if(A!=B) {
            Add_Edge_two(++Dot,B);
            Add_Edge_two(Dot,A);
            Fa[A]=Dot;
            Fa[B]=Dot;
            Res[Dot]=E[i].w2;
            Group++;
        }
        if(Group==Total-1) break;
    }
    DFS(Dot,0);
    while(Test--) {
        int a,b,c;
        scanf("%d %d",&a,&b);
        int X=(K*Last+a-1)%Total+1,Y=(K*Last+b)%(S+1);
        cout<<(Last=Get(X,Y))<<endl;
    }
}

inline void Clean() {
    Cl(Head,0); Cur=0;
    Cl(HHead,0); CCur=0;
    Cl(E,0);
}

int main() {
    // File();
    ios::sync_with_stdio(false);
    cin>>Task;
    while(Task--) {
        Last=0;
        cin>>Total>>Side;
        Clean();
        FOR(i,1,Side) { cin>>E[i].u>>E[i].v>>E[i].w1>>E[i].w2; Add_Edge_one(E[i].v,E[i].u,E[i].w1); Add_Edge_one(E[i].u,E[i].v,E[i].w1); }
        FOR(i,Total+1,(Total<<1)) { Min[i]=INF; }
        Dijkstra();
        cin>>Test>>K>>S;
        Kruskal();
    }
    // fclose(stdin);
    // fclose(stdout);
    system("pause");
    return 0;
}