被 CCF 卡常，P4768归程，平常没卡过不知道怎么处理qwq

//可持久化并查集 by StarsIntoSea_SY
#include <stdio.h>
#include <algorithm>
#include <queue>
#define pii pair<int,int>
#define mid ((l+r)>>1)
using namespace std;
priority_queue<pii,vector<pii>,greater<pii>> q;
const int N=2e5+5; 
struct edge{int to,ne,c;}e[N<<2];
struct EDGE{int x,y,l,h;}E[N<<2];
int c[N<<2],b[N<<2],P[N<<2],num=0,VAL=0;
int n=0,m=0,h[N],dis[N],vis[N],idx=0,tot=0,cnt=0;
int fa[N<<6],lc1[N<<6],rc1[N<<6],rt1[N];
int dep[N<<6],lc2[N<<6],rc2[N<<6],rt2[N];
int depth[N*2];
bool cmp(EDGE x,EDGE y){return x.h>y.h;}
bool CMP(int x,int y){return x>y;}
void add(int a,int b,int c){
	e[++idx]={b,h[a],c};
	h[a]=idx;
}
void build1(int &x,int l,int r){
	x=++tot;
	if(l==r) return void(fa[x]=l);
	build1(lc1[x],l,mid);
	build1(rc1[x],mid+1,r);
}
void insect1(int x,int &y,int l,int r,int k,int c){
	y=++tot;
	lc1[y]=lc1[x],rc1[y]=rc1[x];
	if(l==r) return void(fa[y]=c);
	if(k<=mid) insect1(lc1[x],lc1[y],l,mid,k,c);
	else insect1(rc1[x],rc1[y],mid+1,r,k,c);
}
int query1(int x,int l,int r,int k){
	if(l==r) return fa[x];
	if(k<=mid) return query1(lc1[x],l,mid,k);
	else return query1(rc1[x],mid+1,r,k);
}
void build2(int &x,int l,int r){
	x=++cnt;
	if(l==r) return void(dep[x]=dis[l]);
	build2(lc2[x],l,mid);
	build2(rc2[x],mid+1,r);
}
void insect2(int x,int &y,int l,int r,int k,int c){
	y=++cnt;
	lc2[y]=lc2[x],rc2[y]=rc2[x];
	if(l==r) return void(dep[y]=c);
	if(k<=mid) insect2(lc2[x],lc2[y],l,mid,k,c);
	else insect2(rc2[x],rc2[y],mid+1,r,k,c);
}
int query2(int x,int l,int r,int k){
	if(l==r) return dep[x];
	if(k<=mid) return query2(lc2[x],l,mid,k);
	else return query2(rc2[x],mid+1,r,k);
}
int find(int val,int x){
	int fath=query1(rt1[val],1,n,x);
	if(fath!=x) return find(val,fath);
	return x;
}
void merge(int x,int y){
	x=find(VAL,x),y=find(VAL,y);
	if(x==y) return ;
	if(depth[x]>depth[y]) swap(x,y);
	insect1(rt1[VAL],rt1[VAL+1],1,n,x,y); //fa[x]=y
	depth[y]+=(depth[x]==depth[y]);
	int valx=query2(rt2[VAL],1,n,x);
	int valy=query2(rt2[VAL],1,n,y);
	insect2(rt2[VAL],rt2[VAL+1],1,n,y,min(valx,valy));
	++VAL;
}
void Dij(){
	for(int i=2;i<=n;++i) dis[i]=2147483647;
	dis[1]=0;
	q.push({0,1});
	while(!q.empty()){
		int x=q.top().second;
		q.pop();
		if(vis[x]) continue;
		vis[x]=1;
		for(int i=h[x];i;i=e[i].ne){
			int y=e[i].to;
			int w=e[i].c;
			if(dis[x]+w<dis[y]){
				dis[y]=dis[x]+w;
				q.push({dis[y],y});
			}
		}
	}
}
void sol(){
	for(int i=1;i<=n;++i) depth[i]=dis[i]=vis[i]=h[i]=rt1[i]=rt2[i]=0;
	for(int i=1;i<=m*2;++i) e[i]={0,0,0};
	for(int i=1;i<=cnt;++i) lc2[i]=rc2[i]=dep[i]=0;
	for(int i=1;i<=tot;++i) lc1[i]=lc2[i]=fa[i]=0;
	idx=cnt=tot=VAL=0;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i){
		scanf("%d%d%d%d",&E[i].x,&E[i].y,&E[i].l,&E[i].h);
		add(E[i].x,E[i].y,E[i].l);
		add(E[i].y,E[i].x,E[i].l);
		b[i]=E[i].h;
	}
	Dij();
	build1(rt1[0],1,n);
	build2(rt2[0],1,n);
	sort(E+1,E+1+m,cmp);
	sort(b+1,b+1+m,CMP);
	num=unique(b+1,b+1+m)-b-1;
	int t=0;
	for(int i=1;i<=num;++i){
		while(1){
			if(E[t+1].h==b[i]){
				++t;
				merge(E[t].x,E[t].y);
			}
			else{
				P[i]=VAL;
				break;
			}
			//			if(E[t].h!=b[i]||t>m){
			//				P[i]=VAL;
			//				break;
			//			}
			//			if(f) --t;
			//			++t;f=0;
			//			merge(E[t].x,E[t].y);
		}
	}
	//	for(int i=1;i<=n;++i) printf("%d ",dis[i]);printf("\n");
	//	for(int i=1;i<=num;++i) printf("%d ",P[i]);printf("\n");
	int Q,K,S,lastans=0;scanf("%d%d%d",&Q,&K,&S);
	while(Q--){
		int p,v;scanf("%d%d",&v,&p);
		v=(K*lastans+v-1)%n+1;
		p=(K*lastans+p)%(S+1);
		int L=1,R=num,Mid,r=-1;
		while(L<=R){
			Mid=(L+R)>>1;
			if(b[Mid]==p){r=Mid;break;}
			if(b[Mid]<p) R=Mid-1;
			if(b[Mid]>p) L=Mid+1;
		}
		if(r==-1) r=L-1;
		if(p==b[r]) --r;
		int father=find(P[r],v);
		lastans=query2(rt2[P[r]],1,n,father);
		printf("%d\n",lastans);
	}
}
int main(){
	int T;scanf("%d",&T);
	while(T--) sol();
}