https://www.luogu.com.cn/record/128302512

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5,inf=1e15;
int T,n,m,q,k,s,ans;
int fa[N][21],a[N],f[N];
int head[N],ei,hc[N],dis[N],id;
bool vis[N];
struct edg{
    int u,v,l,a,nxt;
    bool operator<(const edg &t)
    const {return a==t.a?l<t.l:a>t.a;}
}eg[N],egc[N],egs[N];
struct node{
    int u,w;
    bool operator<(const node &t)
    const {return w>t.w;}
};
inline void add(int u,int v,int l,int a){
    egs[++ei]={u,v,l,a,head[u]};head[u]=ei;
}
inline void addc(int u,int v){
    egc[++ei]={u,v,0,0,hc[u]};hc[u]=ei;
}
priority_queue<node>qu;
inline void dijkstra(int s){
    for(int i=1; i<=n; ++i)dis[i]=inf;
    dis[s]=0,qu.push({s,0});
    while(!qu.empty()){
        const int u=qu.top().u;qu.pop();
        if(vis[u])continue;vis[u]=1;
        for(int i=head[u]; i; i=egs[i].nxt){
            const int v=egs[i].v,w=egs[i].l;
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                qu.push({v,dis[v]});
            }
        }
    }
}

inline int find(int x){while(x!=f[x])x=f[x]=f[f[x]];return x;}
inline void Kruskal(){
    sort(eg+1,eg+1+m);id=n;
    for(int i=1; i<=(n<<1); ++i)f[i]=i;
    for(int i=1; i<=m&&id<2*n-1; ++i){
        int u=find(eg[i].u),v=find(eg[i].v);
        a[++id]=eg[i].a,dis[id]=min(dis[u],dis[v]);
        fa[u][0]=fa[v][0]=f[u]=f[v]=id;
        addc(id,u),addc(id,v);
    }
}
inline void dfs(int u){
    for(int i=1; i<21; ++i)
        fa[u][i]=fa[fa[u][i-1]][i-1];
    for(int i=hc[u]; i; i=egc[i].nxt){
        const int v=egc[i].v;
        if(fa[u][0]==v)continue;
        fa[v][0]=u,dfs(v);
    }
}
inline int jump(int u,int x){
    int k=20;for(; ~k; --k){
        if(a[fa[u][k]]>x)u=fa[u][k];
    }return u;
}
inline void init(){ei=ans=0;
    memset(egs,0,sizeof(egs));
    memset(egc,0,sizeof(egc));
    memset(fa,0,sizeof(fa));
    memset(hc,0,sizeof(hc));
    memset(vis,0,sizeof(vis));
    memset(head,0,sizeof(head));
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);dis[0]=-inf;
    cin>>T;while(T--){init();
        cin>>n>>m;int u,v,l,a,p;
        for(int i=1; i<=m; ++i)
            cin>>u>>v>>l>>a,eg[i]={u,v,l,a},
            add(u,v,l,a),add(v,u,l,a);ei=0;
        dijkstra(1);Kruskal();dfs(id);
        cin>>q>>k>>s;while(q--){
            cin>>v>>p;
            v=(v+k*ans-1)%n+1;
            p=(p+k*ans)%(s+1);
            cout<<(ans=dis[jump(v,p)])<<'\n';
        }
    }
    return 0;
}