题目大意：太长了，略
Kruskal重构树，很神奇的一个算法吧
如果两个并查集被某种条件合并，那么这个条件作为一个新的节点连接两个并查集
那么在接下来的提问中，如果某个点合法，它的所有子节点也都合法，即子节点的限制少于父节点
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#define inf 0x3f3f3f3f
#define ll long long
#define il inline
#define N 400100
#define M 800100
using namespace std;
//re
int T,cte,ctb,n,m,tot;
int head[N],hbt[M],fa[M],ff[M][],dis[N],use[N],mi[M],hei[M];
struct EDGE{int to,nxt,val;}edge[M];
struct Krs{int x,y,alt;}krs[N];
struct BT{int to,nxt;}bt[M*];
struct node{int id,dis;};
int cmpk(Krs s1,Krs s2){return s1.alt>s2.alt;}
il node ins(int x1,int x2){node kk;kk.id=x1,kk.dis=x2;return kk;}
bool operator<(const node &s1,const node &s2){return s1.dis>s2.dis;}
int find_fa(int x){
int fx=fa[x],pre;while(fx!=fa[fx])fx=fa[fx];
while(fa[x]!=fx){pre=fa[x],fa[x]=fx,x=pre;}
return fx;
}
int gc(){
int rett=,fh=;char p=getchar();
while(p<''||p>'') {if(fh=='-')fh=-;p=getchar();}
while(p>=''&&p<='') {rett=(rett<<)+(rett<<)+p-'';p=getchar();}
return rett*fh;
}
void clr()
{
cte=ctb=tot=;
memset(fa,,sizeof(fa));memset(ff,,sizeof(ff));
memset(krs,,sizeof(krs));memset(bt,,sizeof(bt));
memset(mi,0x3f,sizeof(mi));memset(edge,,sizeof(edge));
memset(head,-,sizeof(head));memset(hbt,-,sizeof(hbt));
}
void abt(int u,int v){
ctb++;bt[ctb].to=v;
bt[ctb].nxt=hbt[u],hbt[u]=ctb;
}
void ae(int u,int v,int w){
cte++;edge[cte].to=v,edge[cte].val=w;
edge[cte].nxt=head[u],head[u]=cte;
}
void dfs_bt(int x)
{
mi[x]=dis[x];
for(int j=hbt[x];j!=-;j=bt[j].nxt){
int v=bt[j].to;
if(v==ff[x][]) continue;
ff[v][]=v,ff[v][]=x;
dfs_bt(v);
mi[x]=min(mi[x],min(mi[v],dis[v]));
}
}
void get_multip(){
for(int j=;j<=;j++)
for(int i=;i<=tot;i++)
ff[i][j] = ff[ ff[i][j-] ][j-];
}
int multi(int x,int p){
for(int j=;j>=;j--){
if(hei[ff[x][j]]>p) x=ff[x][j];
}return x;
}
void dijkstra()
{
priority_queue<node>que;
memset(dis,0x3f,sizeof(dis));
memset(use,,sizeof(use));
dis[]=,que.push(ins(,));
while(!que.empty()){
node ss=que.top();que.pop();
if(use[ss.id]) continue;
use[ss.id]=;int x=ss.id;
for(int j=head[x];j!=-;j=edge[j].nxt){
int v=edge[j].to;
if(dis[v]>dis[x]+edge[j].val){
dis[v]=dis[x]+edge[j].val;
if(!use[v]) que.push(ins(v,dis[v]));
}
}
}
}
void Kruskal()
{
int fx,fy,sum=;tot=n;
for(int i=;i<=*n;i++) fa[i]=i;
sort(krs+,krs+m+,cmpk);
for(int i=;i<=m;i++){
fx=find_fa(krs[i].x),fy=find_fa(krs[i].y);
if(fx==fy) continue;
abt(++tot,fx),abt(tot,fy);
hei[tot]=krs[i].alt,sum++;
fa[fx]=tot,fa[fy]=tot;
if(sum==n-) break;
}hei[]=-;
dfs_bt(tot);
get_multip();
}
int solve(int x,int p)
{
int fx=multi(x,p);
return mi[fx];
} int main()
{
//freopen("data.in","r",stdin);
scanf("%d",&T);
while(T--)
{ n=gc(),m=gc();clr();
int x,y,w,z,lst=;
for(int i=;i<=m;i++)
{
x=gc(),y=gc(),w=gc(),z=gc();
ae(x,y,w),ae(y,x,w);
krs[i].x=x,krs[i].y=y,krs[i].alt=z;
}
dijkstra();
Kruskal();
int q,k,s;
q=gc(),k=gc(),s=gc();
for(int i=;i<=q;i++)
{
x=gc(),w=gc();
x=(x+k*lst-)%n+;
w=(w+k*lst)%(s+);
lst=solve(x,w);
printf("%d\n",lst);
} }
return ;
}