克鲁斯卡尔重构树模板题。
我们发现，这一题可以拆成两个步骤。第一个步骤，是找到所有u可以通过共享单车达到的点；第二个步骤，是找到这些点中到原点最小的点的距离。
我们容易发现，第一个步骤和长度无关，第二个步骤和海拔无关。
首先考虑第一个步骤。
我们建出一棵克鲁斯卡尔重构树——克鲁斯卡尔重构树是这样的一个数据结构：当你使用克鲁斯卡尔算法建最小/最大生成树的时候，每一次合并，你新建一个节点p，这个点的点权是这一次合并通过的边的边权，然后将即将合并的两个点的根节点合并到p下。这样我们构造出了一棵二叉树，其中所有叶子节点是原图上的节点。
克鲁斯卡尔重构树满足一些有意义的性质。
不妨以这题为例，我们构造一棵最大生成树，那么两点之间的lca的点权就是这两个点之间路径中边权最大的值。换句话说，从u在d的降水下可以到的节点，就是所有和u的lca的点权大于等于d的节点。考虑到这是一棵最大生成树，每个点的父亲节点的点权不会大于这个节点。这也就意味着，我们需要找到u的最高的祖先，使得这个祖先的点权大于等于d。不妨称这个祖先为w，那么w的子树的所有叶子节点，就是u在d的降水下能抵达的节点。
于是，我们求出了第一个步骤的解。
然后我们考虑第二个步骤的解。考虑到这是一张无向图，我们先求出1号节点到所有节点的距离，然后把这些值赋到叶子节点上，不妨称它为『距离权值』。因为我们每一次求min必然是求「某个点的子树中所有叶子节点的『距离权值』的最小值」，那么就可以进行树形dp，把这个最小值的信息直接记录到每个虚拟节点上。
这就做完了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int N=800005,M=800005;
const int INF=0x3f3f3f3f;
inline int Min(int A,int B){
return A<B?A:B;
}
struct ee{
int v;
int w;
int a;
int nxt;
}e[M<<1];
int h[N],et=0;
inline void Eadd(int U,int V,int W,int A){
e[++et]=(ee){V,W,A,h[U]};
h[U]=et;
}
inline void add(int U,int V,int W,int A){
Eadd(U,V,W,A);
Eadd(V,U,W,A);
}
struct tee{
int v;
int nxt;
}te[N<<1];
int g[N],tet=0;
inline void tEadd(int U,int V){
te[++et]=(tee){V,g[U]};
g[U]=et;
}
inline void tadd(int U,int V){
tEadd(U,V);
tEadd(V,U);
}
struct data{
int u;int v;int a;
}lst[M];
inline bool cmp(const data &A,const data &B){
return A.a>B.a;
}
int ff[N],f[N][20];
inline int fa(int X){
return ff[X]==X?ff[X]:ff[X]=fa(ff[X]);
}
int val[N];
int n,m,cnt,rt;
inline void uni(int X,int Y){
X=fa(X),Y=fa(Y);
tadd(ff[X],cnt);tadd(ff[Y],cnt);
ff[X]=ff[Y]=cnt;
}
inline void kruskal(){
cnt=n;
for(int i=1;i<=m;++i){
if(fa(lst[i].u)==fa(lst[i].v)){
continue;
}
val[++cnt]=lst[i].a;
uni(lst[i].u,lst[i].v);
if(cnt==n*2-1){
break;
}
}
rt=fa(1);
}
int dis[N],vis[N];
struct cmp2{
inline bool operator()(int A,int B){
return dis[A]>dis[B];
}
};
priority_queue< int,vector<int>,cmp2 > q;
inline void dij(){
for(int i=2;i<=n*2;++i){
dis[i]=INF;vis[i]=0;
}
vis[1]=1,dis[1]=0;
q.push(1);
int p;
while(!q.empty()){
p=q.top();q.pop();vis[p]=0;
for(int i=h[p];i;i=e[i].nxt){
if(dis[e[i].v]>dis[p]+e[i].w){
dis[e[i].v]=dis[p]+e[i].w;
if(!vis[e[i].v]){
q.push(e[i].v);
}
}
}
}
}
inline void dfs0(int X){
for(int i=g[X];i;i=te[i].nxt){
if(te[i].v==f[X][0]){
continue;
}
// printf("%d %d\n",X,te[i].v);
f[te[i].v][0]=X;
for(int j=1;j<=18;++j){
f[te[i].v][j]=f[f[te[i].v][j-1]][j-1];
}
dfs0(te[i].v);
dis[X]=Min(dis[X],dis[te[i].v]);
}
}
inline int qry(int X,int D){
for(int i=18;i>=0;--i){
if(val[f[X][i]]>D){
X=f[X][i];
}
}
return dis[X];
}
void init(){
scanf("%d%d",&n,&m);
et=tet=0;
for(int i=1;i<=n*2;++i){
g[i]=h[i]=0;
}
int u,v,w,a;
for(int i=1;i<=m;++i){
scanf("%d%d%d%d",&u,&v,&w,&a);
add(u,v,w,a);
lst[i]=(data){u,v,a};
}
std::sort(lst+1,lst+1+m,cmp);
for(int i=1;i<=n*2;++i){
ff[i]=i;val[i]=INF;
}
kruskal();
dij();
dfs0(rt);
// for(int i=1;i<=rt;++i){
// printf("%d ",dis[i]);
// }
// puts("");
int Q,K,S,lans=0,x,d;
scanf("%d%d%d",&Q,&K,&S);
for(int i=1;i<=Q;++i){
scanf("%d%d",&x,&d);
x=(x+lans*K-1)%n+1;d=(d+lans*K)%(S+1);
printf("%d\n",lans=qry(x,d));
}
}
int main(){
int T;
scanf("%d",&T);
while(T--){
init();
}
return 0;
}