```cpp
#include<bits/stdc++.h>
using namespace std;
struct dij
{
int wz,cd;
dij(int wz=0,int cd=0):wz(wz),cd(cd){}
bool operator<(const dij &other)const
{
return cd>other.cd;
}
};
struct edge
{
int u,v,l,a;
bool operator<(const edge &other)const
{
return a<other.a;
}
}e[400005];
int n,m,q,k,s,t1,t2,a[400005],vist[400005],id1[400005],id2[400005],rs2[8400005];
int ls1[8400005],rs1[8400005],ls2[8400005],fa[8400005],dp[8400005],ds[8400005];
long long dist[400005];
vector<pair<int,int> >g[200005];
void build(int x,int l,int r)
{
if(l==r)
{
fa[x]=l,dp[x]=1,ds[x]=dist[l];
return;
}
int mid=l+r>>1;
build(ls1[x]=++t1=ls2[x]=++t2,l,mid);
build(rs1[x]=++t1=rs2[x]=++t2,mid+1,r);
}
void add1(int x,int y,int l,int r,int u,int v)
{
if(l==r)
{
fa[y]=v;
return;
}
int mid=l+r>>1;
ls1[y]=ls1[x],rs1[y]=rs1[x];
if(u<=mid)add1(ls1[x],ls1[y]=++t1,l,mid,u,v);
else add1(rs1[x],rs1[y]=++t1,mid+1,r,u,v);
}
void add2(int x,int y,int l,int r,int u,int v1,int v2)
{
if(l==r)
{
dp[y]=v1,ds[y]=v2;
return;
}
int mid=l+r>>1;
ls2[y]=ls2[x],rs2[y]=rs2[x];
if(u<=mid)add2(ls2[x],ls2[y]=++t2,l,mid,u,v1,v2);
else add2(rs2[x],rs2[y]=++t2,mid+1,r,u,v1,v2);
}
int query1(int x,int l,int r,int u)
{
if(l==r)return fa[x];
int mid=l+r>>1;
if(u<=mid)return query1(ls1[x],l,mid,u);
return query1(rs1[x],mid+1,r,u);
}
int qqu(int x,int u)
{
int d=query1(x,1,n,u);
if(d==u)return d;
return qqu(x,d);
}
pair<int,int> query2(int x,int l,int r,int u)
{
if(l==r)return make_pair(dp[x],ds[x]);
int mid=l+r>>1;
if(u<=mid)return query2(ls2[x],l,mid,u);
return query2(rs2[x],mid+1,r,u);
}
int main()
{
freopen("return.in","r",stdin);
freopen("return.out","w",stdout);
int t;
cin>>t;
while(t--)
{
cin>>n>>m;
for(int i=1;i<=n;i++)g[i].clear();
for(int i=1;i<=m;i++)
{
scanf("%d%d%d%d",&e[i].u,&e[i].v,&e[i].l,&e[i].a);
g[e[i].u].push_back(make_pair(e[i].v,e[i].l));
g[e[i].v].push_back(make_pair(e[i].u,e[i].l));
a[i]=e[i].a;
}
sort(a+1,a+m+1);
sort(e+1,e+m+1);
memset(dist,63,sizeof(dist));
memset(vist,0,sizeof(vist));
dist[1]=0;
priority_queue<dij>pq;
pq.push(dij(1,0));
while(pq.size())
{
dij dd=pq.top();
pq.pop();
if(vist[dd.wz])continue;
int x=dd.wz;
vist[x]=1;
for(int i=0;i<g[x].size();i++)
{
int cu1=g[x][i].first,cu2=g[x][i].second;
if(dist[cu1]>dist[x]+cu2)
{
dist[cu1]=dist[x]+cu2;
pq.push(dij(cu1,dist[cu1]));
}
}
}
cin>>q>>k>>s;
for(int i=0;i<=8400000;i++)
ls1[i]=ls2[i]=rs1[i]=rs2[i]=ds[i]=dp[i]=0;
for(int i=1;i<=m+1;i++)id1[i]=id2[i]=0;
t1=t2=0;
build(id1[m+1]=id2[m+1]=++t1=++t2,1,n);
for(int i=m;i>=1;i--)
{
int u=e[i].u,v=e[i].v;
int fu=qqu(id1[i+1],u),fv=qqu(id1[i+1],v);
pair<int,int> f1=query2(id2[i+1],1,n,fu),f2=query2(id2[i+1],1,n,fv);
if(u==v)
{
id1[i]=id1[i+1],id2[i]=id2[i+1];
continue;
}
if(f1.first<f2.first)swap(f1,f2),swap(fu,fv);
add1(id1[i+1],id1[i]=++t1,1,n,fv,fu);
add2(id2[i+1],id2[i]=++t2,1,n,fu,f1.first+f2.first,min(f1.second,f2.second));
}
int lastans=0;
for(int i=1;i<=q;i++)
{
int v,p;
scanf("%d%d",&v,&p);
v=(v+k*lastans-1)%n+1,p=(p+k*lastans)%(s+1);
int df=upper_bound(a+1,a+m+1,p)-a,fu=qqu(id1[df],v);
pair<int,int> pi=query2(id2[df],1,n,fu);
printf("%d\n",lastans=pi.second);
}
}
return 0;
}
```
by wmy_goes_to_thu @ 2021-03-21 20:35:07
自动 @[ricky0916](/user/289230) @[B_F_S](/user/148507) @[最爱泥三鲶鱼](/user/369836)
by wmy_goes_to_thu @ 2021-03-21 20:41:39
~~@菜鸡们干嘛呀~~
~~反正菜鸡们都不会~~
by ricky0916 @ 2021-03-21 20:50:12
@[ricky0916](/user/289230) 所以您说 B_F_S 和 最爱泥三鲶鱼 都是菜鸡？~~不讲wood~~
by wmy_goes_to_thu @ 2021-03-22 13:19:14