rt，WA on #5~#6,#15~16,TLE on #12~14,#17~20

#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
#define int long long
const int INF=0x7fffffff;
const int N=5e6+10;
struct node{
	int to,nxt,val;
}edge[N];
int head[N];
int cnt1;
void add(int u,int v,int w){
	edge[++cnt1]={v,head[u],w};
	head[u]=cnt1;
}
struct ccf{
	int pos,val;
	friend bool operator<(ccf pre,ccf nxt){
		return pre.val>nxt.val;
	}
};
int n,m,k,ss,cnt2,lst,Q;
priority_queue<ccf> q;
int dis[N];
void dij(){
	for(int i=1;i<=n;i++){
		dis[i]=INF;
	}
	q.push({1,0});
	while(!q.empty()){
		ccf now=q.top();
		q.pop();
		//cout<<"pos:"<<now.pos<<endl;
		if(now.val>=dis[now.pos]) continue;
		dis[now.pos]=now.val;
		for(int i=head[now.pos];i!=-1;i=edge[i].nxt){
			if(dis[edge[i].to]>now.val+edge[i].val){
				q.push({edge[i].to,now.val+edge[i].val});
			}
		}
	}
}
int fa[N];
int find(int x){
	if(fa[x]==x) return x;
	else return fa[x]=find(fa[x]);
}
void connect(int x,int y){
	fa[find(x)]=find(y);
}
struct zyhlqr{
	int ls,rs,fa,minn,val;
}p[N];
int pfind(int x){
	if(p[x].fa==x) return x;
	else return p[x].fa=pfind(p[x].fa); 
}
int st[N][20];
void dfs(int x){
	if(!p[x].ls&&!p[x].rs) return;
	dfs(p[x].ls),dfs(p[x].rs);
	p[x].minn=min(p[p[x].ls].minn,p[p[x].rs].minn);
}
void build_st(){
	for(int j=1;j<19;j++){
		for(int i=1;i<=cnt2;i++){
			st[i][j]=st[st[i][j-1]][j-1];
		}
	}
}
struct xld{
	int p1,p2,val;
}ipt[N];
bool cmp(xld pre,xld nxt){
	return pre.val>nxt.val;
}
int t;
int ask(int x,int y){
	for(int j=18;j>=0;j--){
		if(p[st[x][j]].val>y) x=st[x][j];
	}
	return p[x].minn;
}
signed main(){
//	freopen("return5.in","r",stdin);
//	freopen("return5.out","w",stdout);
	ios::sync_with_stdio(false);
	cin>>t;
	while(t--){
		memset(head,-1,sizeof(head));
		cnt1=0;
		cin>>n>>m;
		cnt2=n;
		for(int i=1;i<=m;i++){
			int uu,vv,ww1,ww2;
			cin>>uu>>vv>>ww1>>ww2;
			add(uu,vv,ww1);add(vv,uu,ww1);
			ipt[i]={uu,vv,ww2};
		}
		sort(ipt+1,ipt+m+1,cmp);
		dij();
//		cout<<"dis:\n";
		for(int i=1;i<=n;i++){
			fa[i]=i;p[i].fa=i;
			p[i].minn=dis[i];
//			cout<<dis[i]<<" ";
		}
//		cout<<endl;
		for(int i=1;i<=m;i++){
			if(find(ipt[i].p1)!=find(ipt[i].p2)){
				int uu=pfind(ipt[i].p1),vv=pfind(ipt[i].p2);
				cnt2++;
				p[cnt2].fa=cnt2;
				p[cnt2].minn=INF;
				p[cnt2].ls=uu,p[cnt2].rs=vv;
				p[uu].fa=p[vv].fa=st[uu][0]=st[vv][0]=cnt2;
				p[cnt2].val=ipt[i].val;
				connect(ipt[i].p1,ipt[i].p2);
			}
		}
//		for(int i=1;i<=cnt2;i++){
//			cout<<i<<":"<<p[i].ls<<" "<<p[i].rs<<endl;
//		}
		dfs(cnt2); 
		build_st();
		cin>>Q>>k>>ss;
		lst=0;
		while(Q--){
			int vv,pp;
			cin>>vv>>pp;
			vv=(vv+k*lst-1)%n+1;
			pp=(pp+k*lst)%(ss+1);
			//cout<<"ask:"<<vv<<" "<<pp<<endl;
			lst=ask(vv,pp);
			cout<<lst<<'\n';
		}
	}
	return 0;
}