RT，用的可持久化并查集做的，虽然用了vector和class，但复杂度感觉没问题，不至于第五个样例要跑好几个小时吧

#include<bits/stdc++.h>
using namespace std;

inline int read(){
	int n=0,f=1;
	char c=getchar();
	while(c<'0' || c>'9'){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0' && c<='9'){
		n=(n<<3)+(n<<1)+(c^48);
		c=getchar();
	}
	return n*f;
}

inline void write(int x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9) write(x/10);
	putchar(x%10^48);
	return;
}

class Persistent_SegmentTree{
	private:
		struct node{
			int left,right,val;
		}Tree[4000050];
		int len,root[200050],nth,kth;
	public:
		void build_tree(int &no,int l,int r,int num[]){
			if(no==0)no=++nth;
			if(l==r){
				Tree[no].val=num[l];
				return;
			}int mid=(l+r)/2;
			build_tree(Tree[no].left,l,mid,num);
			build_tree(Tree[no].right,mid+1,r,num);
		}
		void build(int num[],int L){
			memset(Tree,0,sizeof(Tree));
			len=L;nth=0;kth=0;
			root[0]=0;
			build_tree(root[0],1,len,num);
		}void add(int &no,int l,int r,int Loc,int val){
			if(l==r){
				Tree[nth].val=val;
				return;
			}int mid=(l+r)/2;
			if(mid>=Loc){
				Tree[nth].left=nth+1;
				Tree[nth].right=Tree[no].right;
				nth++;
				add(Tree[no].left,l,mid,Loc,val);
			}else{
				Tree[nth].left=Tree[no].left;
				Tree[nth].right=nth+1;
				nth++;
				add(Tree[no].right,mid+1,r,Loc,val);
			}
		}void change_val(int ver,int loc,int val){
			root[++kth]=++nth;
			add(root[ver],1,len,loc,val);
		}int get_val(int &no,int l,int r,int Loc){
			if(l==r)return Tree[no].val;
			int mid=(l+r)/2;
			if(mid>=Loc)return get_val(Tree[no].left,l,mid,Loc);
			else return get_val(Tree[no].right,mid+1,r,Loc);
		}int num_val(int ver,int loc){
			return get_val(root[ver],1,len,loc);
		}void cpy_ver(int ver){
			root[++kth]=root[ver];
		}
}T_f,T_s;

struct node{
	int to,val;
}N;

struct edge{
	int from,to,depth;
}ed[400050];

struct Dij{
	int no,val;
}tp;

bool operator<(const Dij &x,const Dij &y){
	return x.val>y.val;
}

bool cmp(edge x,edge y){
	return x.depth>y.depth;
}

int Tn,n,m,u,v,l,a,f[200050],siz[200050],deep[400050],version[400050],nth,ver,q,k,s,V,P,lastans,dist[200050],ans;
bool flag[200050];
vector<node> T[200050];
priority_queue<Dij> Q;

int find(int x){
	int fa=T_f.num_val(ver,x);
	if(fa==x)return x;
	return find(fa);
}

void merge(int x,int y){
	int fa_x=find(x);
	int fa_y=find(y);
	if(fa_x==fa_y)return;
	T_f.change_val(ver,fa_x,fa_y);
	T_s.change_val(ver,fa_y,T_s.num_val(ver,fa_x)+T_s.num_val(ver,fa_y));
}

int main()
{
//	freopen("input.txt","r",stdin);
//	freopen("output.txt","w",stdout);
	for(int i=0;i<200050;i++)f[i]=i,siz[i]=1;
	Tn=read();
	while(Tn--){
		lastans=0;nth=0;ver=0;
		memset(flag,0,sizeof(flag));
		memset(deep,0,sizeof(deep));
		memset(version,0,sizeof(version));
		n=read();m=read();
		for(int i=1;i<=n;i++)T[i].clear();
		for(int i=1;i<=m;i++){
			u=read();v=read();l=read();a=read();
			N.to=v;N.val=l;
			T[u].push_back(N);
			N.to=u;
			T[v].push_back(N);
			ed[i].from=u;
			ed[i].to=v;
			ed[i].depth=a;
		}tp.no=1;tp.val=0;
		Q.push(tp);
		while(!Q.empty()){
			tp=Q.top();
			Q.pop();
			if(flag[tp.no]==0){
				flag[tp.no]=1;
				dist[tp.no]=tp.val;
				Dij tmp;
				for(unsigned int i=0;i<T[tp.no].size();i++){
					tmp.no=T[tp.no][i].to;
					tmp.val=T[tp.no][i].val+tp.val;
					Q.push(tmp);
				}
			}
		}sort(ed+1,ed+m+1,cmp);
		T_f.build(f,n);
		T_s.build(siz,n);
		for(int i=1;i<=m;i++){
			int x=ed[i].from,y=ed[i].to;
			if(T_s.num_val(ver,find(x))>T_s.num_val(ver,find(y)))swap(x,y);
			if(find(x)==find(y)){
				if(i==m||ed[i].depth!=ed[i+1].depth){
					nth++;
					deep[nth]=ed[i].depth;
					version[nth]=ver;
				}continue;
			}
			merge(x,y);
			ver++;
			if(i==m||ed[i].depth!=ed[i+1].depth){
				nth++;
				deep[nth]=ed[i].depth;
				version[nth]=ver;
			}
		}deep[0]=2147483647;
		version[0]=0;
		q=read();k=read();s=read();
		while(q--){
			ans=2147483647;
			V=read();P=read();
			V=(V+k*lastans-1)%n+1;
			P=(P+k*lastans)%(s+1);
			int L=0,R=nth+1,mid;
			while(L<R){
				mid=(L+R)/2;
				if(deep[mid]>P)L=mid+1;
				else R=mid;
			}L--;
			if(P==0)L=nth;
			ver=version[L];
			for(int i=1;i<=n;i++)
				if(find(i)==find(V))ans=min(ans,dist[i]);
			write(ans);
			puts("");
			lastans=ans;
		}
	}
	return 0;
}