可持久化并查集的好题啊。。。（flag：补克鲁斯卡尔重构树。。。）
先dijkstra求一下1号点到每个点的距离，再用可持久化并查集维护一下联通性与联通块内哪个点离1号点最近。upper_bound一下，再查询，时间复杂度可行。
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=200005,M=400005;
struct Bian{int x,y,l,a;}b[M];
int T,n,m,c[M],u;
int rt[M<<5],l[M<<5],r[M<<5],cnt,fa[M<<5],ans[M<<5],dep[M<<5],dis[N];
void build(int &k,int L,int R) {
k=++cnt;
int mid=L+R>>1;
if(L==R) {fa[k]=L,ans[k]=dis[L];return;}
build(l[k],L,mid);build(r[k],mid+1,R);
}
void updatefa(int pre,int &k,int L,int R,int pos,int val) {
k=++cnt;l[k]=l[pre];r[k]=r[pre];fa[k]=fa[pre];ans[k]=ans[pre];dep[k]=dep[pre];
if(L==R) {fa[k]=val;return;}
int mid=L+R>>1;
if(pos<=mid) updatefa(l[pre],l[k],L,mid,pos,val);
else updatefa(r[pre],r[k],mid+1,R,pos,val);
}
void updateans(int pre,int &k,int L,int R,int pos,int val) {
k=++cnt;l[k]=l[pre];r[k]=r[pre];fa[k]=fa[pre];ans[k]=ans[pre];dep[k]=dep[pre];
if(L==R) {ans[k]=val;return;}
int mid=L+R>>1;
if(pos<=mid) updateans(l[pre],l[k],L,mid,pos,val);
else updateans(r[pre],r[k],mid+1,R,pos,val);
}
int query(int k,int L,int R,int pos) {
if(L==R) return k;
int mid=L+R>>1;
return (pos<=mid)?query(l[k],L,mid,pos):query(r[k],mid+1,R,pos);
}
void add(int k,int L,int R,int pos) {
if(L==R) {dep[k]++;return;}
int mid=L+R>>1;
if(pos<=mid) {add(l[k],L,mid,pos);}
else {add(r[k],mid+1,R,pos);}
}
int find(int k,int x){
int now=query(k,1,n,x);
while(fa[now]!=x) {
x=fa[now];now=query(k,1,n,x);
}
return now;
}
int head[N],ecnt;
struct Edge{int to,nxt,len,hig;}e[M<<1];
void addedge(int bg,int ed,int len,int hig) {e[++ecnt].hig=hig;e[ecnt].nxt=head[bg];e[ecnt].to=ed;e[ecnt].len=len;head[bg]=ecnt;}
struct Node{int id,dis;bool operator < (const Node &b) const{return dis>b.dis;}};
void dij() {
memset(dis,0x3f,sizeof dis);
dis[1]=0;
priority_queue<Node> q;
q.push((Node){1,0});
while(!q.empty()) {
Node u=q.top();q.pop();
if(u.dis!=dis[u.id]) continue;
for(int i=head[u.id];i;i=e[i].nxt) {
int v=e[i].to;
if(dis[v]>dis[u.id]+e[i].len) {
dis[v]=dis[u.id]+e[i].len;
q.push({v,dis[v]});
}
}
}
}
void merge(int &i,int &x,int &y) {
int fx=find(rt[i],x),fy=find(rt[i],y);
if(fa[fx]!=fa[fy]) {
if(dep[fx]>dep[fy]) swap(fx,fy);
updatefa(rt[i],rt[i],1,n,fa[fx],fa[fy]);
if(ans[fx]<ans[fy]) updateans(rt[i],rt[i],1,n,fa[fy],ans[fx]);
if(dep[fx]==dep[fy]) add(rt[i],1,n,fa[fy]);
}
}
bool cmp(Bian x,Bian y){return x.a<y.a;}
int main() {
scanf("%d",&T);
while(T--) {
ecnt=0;memset(head,0,sizeof head);
scanf("%d%d",&n,&m);
for(int i=1,u,v,l,a;i<=m;i++) {
scanf("%d%d%d%d",&u,&v,&l,&a);
b[i].x=u,b[i].y=v,b[i].l=l,b[i].a=a;
c[i]=a;
addedge(u,v,l,a);addedge(v,u,l,a);
}
dij();
sort(c+1,c+1+m);
sort(b+1,b+1+m,cmp);
u=unique(c+1,c+1+m)-c-1;
cnt=0;int tmp=m;
build(rt[u+1],1,n);
for(int i=u;i;i--) {
rt[i]=rt[i+1];
while(c[i]==b[tmp].a)
merge(i,b[tmp].x,b[tmp].y),tmp--;
}
int x,y,Q,K,S,lastans=0;
scanf("%d%d%d",&Q,&K,&S);
while(Q--) {
scanf("%d%d",&x,&y);
x=(lastans*K+x-1)%n+1;
y=(lastans*K+y)%(S+1);
y=upper_bound(c+1,c+1+u,y)-c;
lastans=ans[find(rt[y],x)];
printf("%d
",lastans);
}
}
return 0;
}