在学习了一波Kruskal重构树后，就来写了一下归程。

题目非常的长看起来非常恶心，仔细读了一下之后发现其实还好。

思路

首先我们需要求一波最短路，求出起点1到所有点的最短路。
然后就是构建一棵Kruskal 重构树
当然是按照海拔高度从大到小排序。

可以轻易发现，只要从v开始找找到了一个w[x]>p的点，求出x子树的所有点到1的dis最小值就行。

根据Kruskal重构树的性质，此时一个节点的子树的权值一定都大于w[x]
也就是一定不会有积水，找到此时最短的距离就行

所以我们需要在树链剖分dfs的时候直接维护一个子树最短的路径。
用倍增不断找这个x的点就行

代码

没有图的封装于是写的比较丑。。。。将就看看

#include <bits/stdc++.h>
#include <cstring>
#include <cmath>
#include <algorithm>
#define ll long long
#define il inline
using namespace std;
const int M=4e5+110;
const int N=2e6+110;
const int inf=(1<<30);
int n,m,head[N],cnt,fa[2*N],deep[N],q,tot,vis[N],coc;
ll dis[N],w[N],last,ans[N];
int head2[N],s,k,father[N][30];
il ll read()
{
    int x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
struct node
{
    int to,nt;
    ll w;
}edge[M*2],e2[M*2];
struct edg
{
    int u,v;
    ll w,h;
}e[N];
bool mmp(edg a,edg b)
{
    return a.h>b.h;
}
il void add(int x,int y)
{
    ++cnt;
    edge[cnt].nt=head[x];
    edge[cnt].to=y;
    head[x]=cnt;
    ++cnt;
    edge[cnt].nt=head[y];
    edge[cnt].to=x;
    head[y]=cnt;
}
il void add_edge(int x,int y,ll w)
{
    e2[++coc]=(node){y,head2[x],w};
    head2[x]=coc;
    e2[++coc]=(node){x,head2[y],w};
    head2[y]=coc;
}
il int findf(int x)
{
    if(x==fa[x])return x;
    else return fa[x]=findf(fa[x]);
}
il void Kruskal_build()
{
    tot=n;
    memset(w,0,sizeof(w));
    for(int i=1;i<=m;i++)
    {
        int fx=findf(e[i].u);
        int fy=findf(e[i].v);
        if(fx==fy)continue;
        tot++;
        add(tot,fx);
        add(tot,fy);
        fa[fx]=tot,fa[fy]=tot;
        w[tot]=e[i].h;

    }
}
il void dfs(int x,int fa1,int d)
{
    deep[x]=d;
    father[x][0]=fa1;
    for(int i=1;(1<<i)<deep[x];i++)
        father[x][i]=father[father[x][i-1]][i-1];
    for(int i=head[x];i;i=edge[i].nt)
    {
        int v=edge[i].to;
        if(v==fa1)continue;
        dfs(v,x,d+1);
        ans[x]=min(ans[x],ans[v]);
    }
}
il void Dijkstra()
{
    for(int i=1;i<=n;i++)dis[i]=(1<<30),vis[i] = 0;
    priority_queue<pair<int,int> ,vector<pair<int,int > >,greater<pair<int,int> > >q;
    q.push(make_pair(0,1));
    dis[1]=0;;
    while(!q.empty())
    {
        int u=q.top().second,w=q.top().first;
        q.pop();
        if(vis[u])continue;vis[u]=1;
        for(int i=head2[u];i;i=e2[i].nt)
        {
            int v=e2[i].to;
            if(dis[v]>dis[u]+e2[i].w)
            {
                dis[v]=dis[u]+e2[i].w;
                q.push(make_pair(dis[v],v));
            }
        }
    }

}
ll query(int x,int p)
{
    for(int i=20;i>=0;i--)
    {
        if((1<<i)<=deep[x]&&w[father[x][i]]>p)
            x=father[x][i];
    }
    return ans[x];
}
int Case;
int main()
{
    Case=read();
    while(Case--)
    {
        n=read();m=read();
        cnt=0,tot=0;coc=0;
        memset(edge,0,sizeof(edge));
        memset(head,0,sizeof(head));
        memset(head2,0,sizeof(head2));
        memset(e2,0,sizeof(e2));
        memset(father, 0, sizeof(father));
        for(int i=1;i<=n;i++)
            fa[i]=i,fa[i+n]=i+n;
        for(int i=1;i<=m;i++)
            e[i].u=read(),e[i].v=read(),e[i].w=read(),e[i].h=read(),add_edge(e[i].u,e[i].v,e[i].w);
        sort(e+1,e+1+m,mmp);
        Dijkstra();
        Kruskal_build();
        int rt=findf(1);
        for(int i=1;i<=n;i++)
            ans[i]=dis[i],ans[i+n]=inf;
        dfs(rt,0,rt);
        last=0;
        q=read();k=read();s=read();
        for(int i=1;i<=q;i++)
        {
            int v0,v;
            ll p0,p;
            v0=read();p0=read();
            v=(v0+k*last-1)%n+1;
            p=(p0+k*last)%(s+1);
            last=query(v,p);
            printf("%lld\n",last);
        }

    }

    return 0;
}