使用的是可持久化并查集，莫名其妙T飞为64分。

加了快读、O2也还是64分，不知道是人傻常数大还是复杂度假掉，但最容易出错的按秩合并经检查应该没有问题。

代码：

#include<bits/stdc++.h>

using namespace std;

const int N=200000,M=400000,Q=400000,LGN=20;
const int INF=0x3f3f3f3f;

int n,m,q,k,s;
int head[N+10],te;
int d[N+10];
bool lck[N+10];
int rt[M+10];

struct PST{
	#define mid ((l+r)>>1)
	int ls[M*LGN],rs[M*LGN],v[M*LGN],tn;
	int rt[M],trt;
	
	void Clear(){
		tn=trt=0;
	}
	
	void Build_d(int &u,const int &l,const int &r){
		u=tn++;
		if(l==r)v[u]=d[l];
		else Build_d(ls[u],l,mid),Build_d(rs[u],mid+1,r);
	}
	
	void Build(int &u,const int &l,const int &r,const int &x){
		u=tn++;
		if(l==r)v[u]=x;
		else Build(ls[u],l,mid,x),Build(rs[u],mid+1,r,x);
	}

	void Add(int &u,const int &old,const int &l,const int &r,const int &x,const int &y){
		u=tn++;
		if(l==r){
			v[u]=y;
			return;
		}
		ls[u]=ls[old],rs[u]=rs[old];
		if(x>mid)Add(rs[u],rs[old],mid+1,r,x,y);
		else Add(ls[u],ls[old],l,mid,x,y);
	}

	int Query(const int &u,const int &l,const int &r,const int &x){
		if(l==r)return v[u];
		if(x>mid)return Query(rs[u],mid+1,r,x);
		return Query(ls[u],l,mid,x);
	}
	#undef mid
};

struct PUFS{
	PST f,dep,ans;

	void Build(){
		f.Clear();
		dep.Clear();
		ans.Clear();
		f.Build(f.rt[f.trt++],1,n,-1);
		dep.Build(dep.rt[dep.trt++],1,n,1);
		ans.Build_d(ans.rt[ans.trt++],1,n);
	}

	int Find(const int &old,const int &x){
		int ls=f.Query(f.rt[old],1,n,x);
		return ~ls?Find(old,ls):x;
	}

	void Union(const int &old,int x,int y){
		x=Find(old,x),y=Find(old,y);
		int dx=dep.Query(dep.rt[old],1,n,x),dy=dep.Query(dep.rt[old],1,n,y),ax=ans.Query(ans.rt[old],1,n,x),ay=ans.Query(ans.rt[old],1,n,y);
		if(x!=y){
			if(dx>dy)swap(x,y),swap(dx,dy);
			f.Add(f.rt[f.trt++],f.rt[old],1,n,y,x);
			if(dx==dy)dep.Add(dep.rt[dep.trt++],dep.rt[old],1,n,x,dx+1);
			else dep.rt[dep.trt++]=dep.rt[old];
			ans.Add(ans.rt[ans.trt++],ans.rt[old],1,n,x,min(ax,ay));
		}
		else f.rt[f.trt++]=f.rt[old],dep.rt[dep.trt++]=dep.rt[old],ans.rt[ans.trt++]=ans.rt[old];
	}
	
	int Get(const int &old,int x){
		x=Find(old,x); 
		return ans.Query(ans.rt[old],1,n,x);
	}
}st;

struct edge{
	int v,nex,d,h;
}e[M*2+10];

struct edge_{
	int u,v,d,h;
	
	bool operator<(const edge_ &x)const{
		return h>x.h;
	}
}ee[M+10];

struct node{
	int id,d;

	bool operator<(const node &x)const{
		return d>x.d;
	}
};

void Adde(int u,int v,int d,int h){
	e[++te].nex=head[u];
	e[te].v=v;
	e[te].d=d;
	e[te].h=h;
	head[u]=te;
}

void Add(edge_ x){
	Adde(x.u,x.v,x.d,x.h);
	Adde(x.v,x.u,x.d,x.h);
}

node Node(int id,int d){
	node res;
	res.id=id;
	res.d=d;
	return res;
}

void Dij(){
	priority_queue<node> pq;
	d[1]=0;
	pq.push(Node(1,0));
	while(!pq.empty()){
		int u=pq.top().id;
		pq.pop();
		if(lck[u])continue;
		lck[u]=1;
		for(register int i=head[u];i;i=e[i].nex){
			int v=e[i].v,dis=e[i].d;
			if(!lck[v]&&d[v]>d[u]+dis){
				d[v]=d[u]+dis;
				pq.push(Node(v,d[v]));
			}
		}
	}
}

inline int read(){
	char c=getchar();
	int res=0,f=1;
	while(c>'9'||c<'0')f=(c=='-'?-1:f),c=getchar();
	while(c>='0'&&c<='9')res=res*10+c-'0',c=getchar();
	return res*f;
}

int main(){
	int T=read();
	while(T--){
		memset(lck,0,sizeof lck);
		memset(d,0x3f,sizeof d);
		memset(head,0,sizeof head);
		te=0;
		n=read(),m=read();
		for(register int i=0;i<m;i++)
			ee[i].u=read(),ee[i].v=read(),ee[i].d=read(),ee[i].h=read(),Add(ee[i]);
		Dij();
		st.Build();
		sort(ee,ee+m);
		rt[0]=INF;
		for(register int i=0;i<m;i++)st.Union(i,ee[i].u,ee[i].v),rt[i+1]=ee[i].h;
		q=read(),k=read(),s=read();
		for(register int i=0,last=0;i<q;i++){
			int v=read(),p=read();
			v=(v+k*last-1)%n+1;
			p=(p+k*last)%(s+1);
			int l=0,r=m;
			while(l<r){
				int mid=(l+r+1)>>1;
				if(rt[mid]<=p)r=mid-1;
				else l=mid;
			}
			printf("%d\n",last=st.Get(l,v));
		}
	}
	return 0;
}