闲话
一个蒟蒻，在网络同步赛上进行了这样的表演——
T2组合计数不会，T3字符串数据结构不会，于是爆肝T1
一开始以为整个地图都有车，然后写了2h+的树套树，终于发现样例过不去
然后写可持久化并查集Debug到13:20过了前4个样例，然后第5个T飞了。
FST？
。。。。。。
FST！
完美收获50分暴力分。
原来是按秩合并那里咕咕了。
从50到100的蜕变，只需一行，你值的拥有。
思路
不会kruscal重构树
容易发现，假设我们确定了水位线，那么就确定了图中有哪些边是连通的。这时候的答案该如何确定呢？因为车可以在一个连通块里随便开，所以同一个连通块里的点的答案都是一样的，为连通块内离\(1\)最近的点到\(1\)的距离。
那当然要首先把单源最短路求出来。SPFA死了？被固定了？（参考生物必修3），还好蒟蒻写的是dijkstra。
因为并查集只能合并，所以我们要按高度从大到小排序依次加边。如果是离线那好办了，把询问也按高度排个序，每在并查集里加一条边就可以完成若干个询问。
那强制在线？当然要把合并过程中的每个版本都存起来啦！用可持久化并查集（蒟蒻之前写过一篇blog）
当然，高度要离散化，为了让每个询问通过二分找到对应版本。
复杂度\(O(n\log m+(m+q)\log^2n)\)，当然这里写的有点丑，在倒序合并的过程中可以在外面放并查集，祖先到并查集里跳，比在可持久化并查集里跳快多了，复杂度\(O(n\log m+m\log n+q\log^2n)\)。
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#define UI unsigned int
#define RG register
#define I inline
#define R RG UI
#define G c=getchar()
using namespace std;
const int N=2e5+9,M=8e5+9,S=2e7;
struct NODE{
UI u,d;
I bool operator<(RG NODE x)const{return d>x.d;}
};//堆优化dijkstra的节点
struct EDGE{
UI u,v,a;
I bool operator<(RG EDGE x)const{return a<x.a;}
}e[M];//对边排序
priority_queue<NODE>q;
UI n,L,p,he[N],ne[M],to[M],l[M],a[M],b[M],d[N],rt[M],lc[S],rc[S],f[S],mn[S],dep[S];
bool vis[N];
I UI in(){
RG char G;
while(c<'-')G;
R x=c&15;G;
while(c>'-')x*=10,x+=c&15,G;
return x;
}
void build(R&u,R l,R r){//建初始并查集
u=++p;
if(l==r){mn[u]=d[f[u]=l];return;}
R m=(l+r)>>1;
build(lc[u],l,m);
build(rc[u],m+1,r);
}
UI ins(R*u,R v,R t){//插入
R l=1,r=n,m;
while(l!=r){
*u=++p;m=(l+r)>>1;
if(t<=m)r=m,rc[*u]=rc[v],u=lc+*u,v=lc[v];
else l=m+1,lc[*u]=lc[v],u=rc+*u,v=rc[v];
}
return *u=++p;
}
UI getf(R rt,R t){//跳祖先
R u,l,r,m;
while(1){
u=rt;l=1;r=n;
while(l!=r){
m=(l+r)>>1;
if(t<=m)r=m,u=lc[u];
else l=m+1,u=rc[u];
}
if(t==f[u])break;
t=f[u];
}
return u;
}
int main(){
freopen("return.in","r",stdin);
freopen("return.out","w",stdout);
R T=in(),m,i,j,u,v,w;
while(T--){
p=0;n=in();m=in();//时刻注意清空变量！
for(i=1;i<=m;++i){
u=in();v=in();
ne[++p]=he[u];to[he[u]=p]=v;
ne[++p]=he[v];to[he[v]=p]=u;
l[p]=l[p-1]=in();
e[i]=(EDGE){u,v,a[p]=a[p-1]=in()};
}
memset(d,-1,(n+1)<<2);//dijkstra开始
p=d[1]=0;q.push((NODE){1,0});
while(!q.empty()){
RG NODE cur=q.top();q.pop();
if(vis[u=cur.u])continue;
vis[u]=1;
for(i=he[u];i;i=ne[i])
if(d[to[i]]>d[u]+l[i])
q.push((NODE){to[i],d[to[i]]=d[u]+l[i]});
}
R q=in(),k=in(),s=in(),lans=0;
sort(e+1,e+m+1);
for(i=1;i<=m;++i)b[i]=e[i].a;
b[m+1]=s+1;L=unique(b+1,b+m+2)-b-1;//离散化，注意加入s+1
build(rt[L],1,n);
for(i=L-1,j=m;i;--i){
rt[i]=rt[i+1];
for(;j&&e[j].a==b[i];--j){
if((u=getf(rt[i],e[j].u))==(v=getf(rt[i],e[j].v)))continue;//可优化的地方
if(dep[u]>dep[v])swap(u,v);//按秩合并
f[ins(&rt[i],rt[i],f[u])]=f[v];
w=ins(&rt[i],rt[i],f[v]);
f[w]=f[v];mn[w]=min(mn[u],mn[v]);//因为按秩合并所以min必须要记
dep[w]=dep[v]+(dep[u]==dep[v]);//50分就是因为这一行！
}
}
while(q--){
v=(in()+k*lans-1)%n+1;u=(in()+k*lans)%(s+1);
printf("%u\n",lans=mn[getf(rt[upper_bound(b+1,b+L+1,u)-b],v)]);
}//谨慎选择lower_bound和upper_bound
memset(vis,0,n+1);
memset(he,0,(n+1)<<2);
memset(rt,0,(L+1)<<2);
memset(lc,0,(p+1)<<2);
memset(rc,0,(p+1)<<2);
memset(f,0,(p+1)<<2);
memset(mn,0,(p+1)<<2);
memset(dep,0,(p+1)<<2);//该清空的都要清空
}
return 0;
}