RT

调了一上午，本来写了个可持久并查集模板很开心，想到归程这题也是可持久并查集，就想试一试，发现写半天就顶不住了，看题解也没有码风一样的，所以求求大佬帮助，口胡一下或者改改我的代码也行，目前是WA了，MLE、TLE、RE先不管了。

谢谢大佬们。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int M=4e5+10;
const int N=4e5+10;
const int MAX=1e7;
int n,m;

struct node{
	int next,u,v,h,s;
}e[M];
int head[M];
int cc=1;

void addd(int u,int v,int s,int h){//加边 
	e[cc].v=v;
	e[cc].u=u;
	e[cc].s=s;
	e[cc].h=h;
	e[cc].next=head[u];
	head[u]=cc++;
}
bool cmp(node g,node h){
	return g.h>h.h;
}

struct ss{
	int fa,h,ls,rs;
	ll d;
}a[MAX];
int ti[MAX];
int cnt=0;
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;
}

ll dis[N];
int vis[N]; 
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
void dijkstra(){
	dis[1]=0;
	q.push(make_pair(0,1));	
	while(!q.empty()){
		pair<int,int> osa=q.top();
		q.pop();
		int id=osa.second;
		if(vis[id]==1) continue;
		vis[id]=1;
		for(int i=head[id];~i;i=e[i].next){
			int y=e[i].v;
 			if(vis[y]==1) continue;
			if(dis[y]>dis[id]+e[i].s){
				dis[y]=dis[id]+e[i].s;
				q.push(make_pair(dis[y],y));
			}
		}
	}
}
 
int ad(int x){
	a[++cnt]=a[x];
	return cnt;
}
int build(int l,int r){
	int to=++cnt;
	if(l==r){
		a[to].fa=l;
		a[to].d=dis[l];
		return to;
	}
	int mid=(l+r)>>1;
	a[to].ls=build(l,mid);
	a[to].rs=build(mid+1,r);
	return to;
}
int ff(int now,int l,int r,int x){
	if(l==r) return now;
	int mid=(l+r)>>1;
	if(mid>=x) return ff(a[now].ls,l,mid,x);	
	else return ff(a[now].rs,mid+1,r,x);
}
int find(int now,int x){
	int fa=ff(ti[now],1,n,x);
	if(a[fa].fa==x){
		return fa;
	}
	int result=find(now,a[fa].fa);
	a[fa].fa=a[result].fa;
	return result;
}
int o;
int hb(int now,int l,int r,int x,int f){
	int to=ad(now);
	if(l==r){
		a[to].fa=f;
		o=to;
		return to;
	}
	int mid=(l+r)>>1;
	if(mid>=x){
		a[to].ls=hb(a[now].ls,l,mid,x,f);
	}
	else{
		a[to].rs=hb(a[now].rs,mid+1,r,x,f);
	}
	return to;
}

int add(int now,int l,int r,int x){
	int to=ad(now);
	if(l==r){
		a[to].h++;
		a[to].d=min(a[to].d,a[o].d);
		return to;
	}
	int mid=(l+r)>>1;
	if(mid>=x)
		a[to].ls=add(a[now].ls,l,mid,x);
	else
		a[to].rs=add(a[now].rs,mid+1,r,x);
	return to;
}
void merge(int now,int x,int y){
	x=find(now,x),y=find(now,y);
	if(a[x].fa!=a[y].fa){
		if(a[x].h>a[y].h)
			swap(x,y);
		o=0;
		ti[now]=hb(ti[now-1],1,n,a[x].fa,a[y].fa);
//		if(a[x].h==a[y].h)
			ti[now]=add(ti[now],1,n,a[y].fa);
	}
}

void rest(){
	cc=1;
	cnt=0;
	memset(head,-1,sizeof head);
	memset(e,0,sizeof e);
	memset(a,0,sizeof a);
	memset(dis,0x3f,sizeof dis);
	memset(vis,0,sizeof vis);
	memset(ti,0,sizeof ti);
}

int search(int x){
	int l=1,r=cc,mid,res=0;
	while(l<=r){
		mid=(l+r)>>1;
		if(e[mid].h>x){
			res=mid,l=mid+1;
		}
		else{
			r=mid-1;
		}
	}
	return res;
}

void solve(){
	n=read(),m=read();
	
	for(int i=1;i<=m;i++){
		int u,v,s,h;
		u=read(),v=read(),s=read(),h=read();
		addd(u,v,s,h);
		addd(v,u,s,h);
	}
	dijkstra();
	cc--;
	sort(e+1,e+cc+1,cmp);
	
	ti[0]=build(1,n);
	
	for(int i=1;i<=cc;i++){
		ti[i]=ti[i-1];
		merge(i,e[i].u,e[i].v);
	}
	
	int q,k,s,lastans=0,ans;
	q=read(),k=read(),s=read();
	while(q--){
		int v,p;
		v=read(),p=read();	
		v=(v+k*lastans-1)%n+1;
		p=(p+k*lastans)%(s+1);
		int pos=search(p);
		int loc=find(pos,v);
		ans=a[loc].d;
		lastans=ans;
		cout<<ans<<"\n";
	}
} 

signed main(){
    ios::sync_with_stdio(false);
//    freopen("return7.in","r",stdin);
//    freopen("return.out","w",stdout);
    int t;
    t=read();
    while(t--){
		rest();
    	solve();
	}
    return 0;
}