#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#define N 200100
#define M 400100
#define INF 0x3f3f3f3f
using namespace std;

int head1[N],head2[N<<1],fa[N<<1][20],cnt1,cnt2,val[N<<1],ver[N<<1],vis[N],dis[N<<1];

struct Node0{
    int u,v,h;
    bool operator < (const Node0 &x)const{
        return h>x.h;
    }
}edge0[M];
struct Node1{
    int to,next,w;
}edge1[M<<1];
struct Node2{
    int to,next;
}edge2[N<<2];

void addEdge1(int from,int to,int w){
    edge1[cnt1]=(Node1){to,head1[from],w};
    head1[from]=cnt1++;
    edge1[cnt1]=(Node1){from,head1[to],w};
    head1[to]=cnt1++;
}

void addEdge2(int from,int to){
    edge2[cnt2]=(Node2){to,head2[from]};
    head2[from]=cnt2++;
    edge2[cnt2]=(Node2){from,head2[to]};
    head2[to]=cnt2++;
}

void init(int n){
    cnt1=cnt2=0;
    memset(head1,-1,sizeof(head1));
    memset(head2,-1,sizeof(head2));
    memset(fa,0,sizeof(fa));
    memset(vis,0,sizeof(vis));
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0;
    for(int i=1;i<=n;i++)
        ver[i]=i;
}

int find(int x){
    return ver[x]==x?x:(ver[x]=find(ver[x]));
}

void Dijkstra(int s){
    priority_queue<pair<int,int> > Q;
    Q.push(make_pair(dis[s],s));
    int u,v;
    while(!Q.empty()){
        u=Q.top().second;
        Q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=head1[u];i!=-1;i=edge1[i].next){
            v=edge1[i].to;
            if(dis[v]>dis[u]+edge1[i].w){
                dis[v]=dis[u]+edge1[i].w;
                Q.push(make_pair(-dis[v],v));
            }
        }
    }
}

void kruskal(int n,int m){
    int num=n,x,y;
    for(int i=0;i<m;i++){
        x=find(edge0[i].u);
        y=find(edge0[i].v);
        if(x!=y){
            num++;
            ver[x]=ver[y]=num;
            val[num]=edge0[i].h;
            addEdge2(x,num);
            addEdge2(y,num);
            if(num - n == n-1) return;
        }
    }
}

void dfs(int u,int fath){
    fa[u][0]=fath;
    for(int i=1;i<=19;i++)
        fa[u][i]=fa[fa[u][i-1]][i-1];
    for(int i=head2[u];i!=-1;i=edge2[i].next){
        int v=edge2[i].to;
        if(v!=fath){
            dfs(v,u);
            dis[u]=min(dis[u],dis[v]);
        }
    }
}

int lca(int x,int h){
    for(int i=19;i>=0;i--){
        if(fa[x][i] && val[fa[x][i]]>h)
            x=fa[x][i];
    }
    return dis[x];
}

int main(){
    int T,n,m,u,v,l,h,Q,K,S,v0,p0,p,lastans=0;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        init(2*n);
        for(int i=0;i<m;i++){
            scanf("%d%d%d%d",&u,&v,&l,&h);
            edge0[i].u=u,edge0[i].v=v,edge0[i].h=h;
            addEdge1(u,v,l);
        }
        Dijkstra(1);
        sort(edge0,edge0+m);
        kruskal(n,m);
        dfs(2*n-1,0);
        scanf("%d%d%d",&Q,&K,&S);
        while(Q--){
            scanf("%d%d",&v0,&p0);
            v=(v0+K*lastans-1)%n+1;
            p=(p0+K*lastans)%(S+1);
            lastans=lca(v,p);
            printf("%d\n",lastans);
        }
    }
    return 0;
}