```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){//快读
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
inline void write(int x){//快写
if(x<0){putchar('-');x=-x;}
if(x>9)write(x/10);
putchar(x%10+'0');
}
const int N=8e5+5;
const int M=20;
const int INF=0x3f3f3f3f;
int n,m,lastans,q,k,s,tot,tot1;
int vis[N],head[N],head1[N],dep[N],dis[N],fa[N],f[N][M];
struct node{
int u,v,l,a;
bool operator <(const node &qwq) const{
return a>qwq.a;
}
}e[N],p[N<<1];
struct edge{
int nxt,to;
}pool[N<<1];
struct Edge{//1
int w,nxt,to;
}Pool[N];
struct heap{
int v,w;
bool operator <(const heap &qwq) const{
return w>qwq.w;
}
};
inline int find(int x){
if(fa[x]==x)return fa[x];
else return fa[x]=find(fa[x]);
}
inline void add(int u,int v){
pool[++tot].to=v;
pool[tot].nxt=head[u];
head[u]=tot;
}
inline void add1(int u,int v,int w){
Pool[++tot1].to=v;
Pool[tot1].w=w;
Pool[tot1].nxt=head1[u];
head1[u]=tot1;
}
void dij(){
s=1;
priority_queue <heap> q;
for(int i=1;i<=n;i++)dis[i]=INF,vis[i]=0;
dis[s]=0;
q.push((heap){s,0});
while(!q.empty()){
int u=q.top().v;q.pop();
if(vis[u])continue;
vis[u]=1;
for(int i=head1[u];i;i=Pool[i].nxt){
int v=Pool[i].to;
if(dis[u]+Pool[i].w<dis[v]){
dis[v]=dis[u]+Pool[i].w;
q.push((heap){v,dis[v]});
}
}
}
for(int i=1;i<=n;i++)p[i].l=dis[i];
}
inline void dfs(int u,int Fa){
dep[u]=dep[Fa]+1,f[u][0]=Fa;
for(int i=1;i<=M-1;i++)
f[u][i]=f[f[u][i-1]][i-1];
for(int i=head[u];i;i=pool[i].nxt){
int v=pool[i].to;
dfs(v,u);
p[u].l=min(p[u].l,p[v].l);
}
}
int query(int x,int y){
for(int i=M-1;i>=0;i--)
if(dep[x]-(1<<i)>0&&p[f[x][i]].a>y)
x=f[x][i];
return p[x].l;
}
inline void init(){
tot=0,tot1=0;
memset(e,0,sizeof(e));
memset(f,0,sizeof(f));
memset(head,0,sizeof(head));
memset(head1,0,sizeof(head1));
}
void kruskal(){
int cnt=n,num=0;
for(int i=1;i<=(n<<1);i++)fa[i]=i;
sort(e+1,e+m+1);
for(int i=1;i<=m;i++){
int u=e[i].u,v=e[i].v;
int fx=find(u),fy=find(v);
if(fx!=fy){
++cnt;
add(cnt,fx),add(cnt,fy);
fa[fx]=cnt,fa[fy]=cnt;
p[cnt].a=e[i].a;
++num;
}
if(num==n-1)break;
}
dfs(cnt,0);
}
void solve(){
init();
n=read(),m=read();
for(int i=1;i<=m;i++){
e[i].u=read(),e[i].v=read(),e[i].l=read(),e[i].a=read();
add1(e[i].u,e[i].v,e[i].l);
add1(e[i].v,e[i].u,e[i].l);
}
for(int i=n+1;i<=(n<<1);i++)p[i].l=INF;
dij();
q=read(),k=read(),s=read();
kruskal();
while(q--){
int v0=read(),p0=read();
int x=(k*lastans+v0-1)%n+1;
int y=(k*lastans+p0)%(s+1);
lastans=query(x,y);
write(lastans);puts("");
}
}
signed main(){
int t=read();
while(t--)solve();
return 0;
}
```
by Dream_weavers @ 2023-01-17 20:35:07
@[Dream_weavers](/user/572482) 建议找dls
by winter2020 @ 2023-01-18 16:24:56
考咕，yzl tq我爱你
by starry_sky_155 @ 2023-07-18 12:10:39
考咕
by littleone @ 2023-07-18 12:16:09
靠 咕
by Stanley8231 @ 2023-07-18 12:23:07
> 题单不是发了么
>有时间在这里bb不如去刷题是吧
by winter2020 @ 2023-07-18 19:42:40