TLE on #6，12，13，14

#include<bits/stdc++.h>
using namespace std;
template <class T>
inline T read(){
    T r=0,f=0;char c=getchar();
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) r=(r<<3)+(r<<1)+(c^48),c=getchar();
    return f?-r:r;
}
const int N=4e5+5,INF=1e9;
struct edge{int from,to,val;}e[N];
struct zfz{
    int u,val;
    bool operator <(const zfz x)const{return x.val<val;}
};
int n,m,ans;
int dis[N];
bool vis[N];
int ff[N],val[N],cnt;
int hd[N],to[N],nx[N],tote;
int hd2[N],to2[N],nx2[N],val2[N],tote2;
int fa[N][25],Min[N];
void adde(int u,int v){nx[++tote]=hd[u];to[tote]=v;hd[u]=tote;}
void adde2(int u,int v,int c){
    nx2[++tote2]=hd2[u];to2[tote2]=v;hd2[u]=tote2;val2[tote2]=c;
    nx2[++tote2]=hd2[v];to2[tote2]=u;hd2[v]=tote2;val2[tote2]=c;
}
int find(int x){return ff[x]==x?x:ff[x]=find(ff[x]);}
void dij(){
    priority_queue<zfz> q;
    memset(dis,0x7f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    q.push((zfz){1,0});dis[1]=0;
    while(!q.empty()){
        int u=q.top().u;q.pop();
        if(vis[u]) continue;
        vis[u]=true;
        for(int i=hd2[u];i;i=nx2[i]){
            int v=to2[i];
            if(dis[v]>dis[u]+val2[i]){
                dis[v]=dis[u]+val2[i];
                if(!vis[v]) q.push((zfz){v,dis[v]});
            }
        }
    }
}
void dfs(int u,int father){
    fa[u][0]=father;
    for(int i=1;i<=20;++i) fa[u][i]=fa[fa[u][i-1]][i-1];
    if(!hd[u]) Min[u]=dis[u];
    for(int i=hd[u];i;i=nx[i]){
        int v=to[i];
        dfs(v,u);
        Min[u]=min(Min[u],Min[v]);
    }
}
void kruskal(){
    sort(e+1,e+1+m,[](edge x,edge y){return x.val>y.val;});
    for(int i=1;i<=(n<<1)-1;++i) ff[i]=i;
    for(int i=1;i<=m;++i){
        int x=find(e[i].from),y=find(e[i].to);
        if(x!=y){
            val[++cnt]=e[i].val;
            ff[x]=ff[y]=ff[cnt]=cnt;
            adde(cnt,x),adde(cnt,y);
        }
    }
    dfs(cnt,0);
}
void query(int x,int c){
    for(int i=20;i>=0;--i) if(fa[x][i]&&val[fa[x][i]]>c) x=fa[x][i];
    printf("%d\n",ans=Min[x]);
}
void init(){
    memset(fa,0,sizeof(fa));
    memset(hd,0,sizeof(hd));
    memset(hd2,0,sizeof(hd2));
    memset(Min,0x7f,sizeof(Min));
    tote=tote2=ans=0;
}
int main(){
    for(int T=read<int>();T;--T){
        init();
        cnt=n=read<int>(),m=read<int>();
        for(int i=1;i<=m;++i){
            int x=read<int>(),y=read<int>(),z=read<int>(),a=read<int>();
            e[i]=(edge){x,y,a};adde2(x,y,z);
        }
        dij(),kruskal();
        for(int Q=read<int>(),k=read<int>(),s=read<int>();Q;--Q){
            int x=(read<int>()+k*ans-1)%n+1,y=(read<int>()+k*ans)%(s+1);
            query(x,y);
        }
    }
    return 0;
}