#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=1E6+10;
struct node
{
	int st,en,l,h;
	node(){st=en=l=h=0;}
	node(int x,int y,int a,int z){st=x;en=y;l=a;h=z;}
}a[N];
struct data
{
	int bh,net,l,h;
	data(){bh=net=l=h=0;}
	data(int x,int y,int a,int z){bh=x;net=y;l=a;h=z;}
}b[N],c[N],tr[N];
int cnt,h[N],deep[N],fa[N/10][20],h2[N],cntt;
int insert(int x,int y,int z,int p)
{
	b[++cnt]=data(y,h[x],z,p);
	h[x]=cnt;
}
int insert2(int x,int y,int z,int p)
{
	tr[++cntt]=data(y,h2[x],z,p);
	h2[x]=cntt;
}
int f[N],d[N];
int find(int x)
{
	if(f[x]!=x) f[x]=find(f[x]);
	return f[x];
}
bool vis[N];
int t,n,m,q,k,s,lastans=0,v,p,point;
void dij(int st)
{
	memset(d,0x3f3f3f3f,sizeof(d));
	memset(vis,0,sizeof(vis));
	d[st]=0;
	priority_queue<PII,vector<PII>,greater<PII> >he;
	he.push({0,st});
	while(!he.empty())
	{
		PII k=he.top();
		int dis=k.first,bh=k.second;
		he.pop();
		if(vis[bh]) continue;
		vis[bh]=1;
		for(int i=h2[bh];i!=0;i=tr[i].net)
		{
			int j=tr[i].bh;
			if(d[j]>dis+tr[i].l)
			{
				d[j]=dis+tr[i].l;
				he.push({d[j],j});
			}
		}
	}
	for(int i=1;i<=n;i++) c[i].l=d[i];
}
bool cmp(node a,node b) { return a.h>b.h; }
void EX_kruskal()
{
	for(int i=1;i<=m;i++)
	{
		int fx=find(a[i].st),fy=find(a[i].en);
		if(fx!=fy)
		{
			point++;
			f[fx]=f[fy]=point;
			insert(fx,point,0,a[i].h);
			insert(point,fx,0,a[i].h);
			insert(point,fy,0,a[i].h);
			insert(fy,point,0,a[i].h);
    		c[point].h=a[i].h;
			c[point].l=min(c[fx].l,c[fy].l);
			if(point==2*n-1) return;
		}
	}
}
void dfs(int now,int father)
{
	deep[now]=deep[father]+1;fa[now][0]=father;
	for(int i=1;i<=19;i++) fa[now][i]=fa[fa[now][i-1]][i-1];
	for(int i=h[now];i!=0;i=b[i].net)
	{
		int j=b[i].bh;
		if(j!=father)
		{
			dfs(j,now);
			if(now>n) c[now].l=min(c[j].l,c[now].l);
		}
	}
}
int query(int x,int y)
{
	for(int i=19;i>=0;i--) if(deep[x]-(1<<i)>0&&c[fa[x][i]].h>y) x=fa[x][i];
	return c[x].l;
}
int main()
{
	cin>>t;
	while(t--)
	{
		cin>>n>>m;
		memset(h,0,sizeof(h));
		memset(h2,0,sizeof(h2));
		for(int i=1;i<=2*n;i++) a[i]=node(0,0,0,0);
		for(int i=1;i<=cnt;i++) b[i]=data(0,0,0,0),c[i]=data(0,0,0,0);
		for(int i=1;i<=cntt;i++) c[i]=data(0,0,0,0),tr[i]=data(0,0,0,0);
		cnt=cntt=0;
		for(int i=1;i<=2*n;i++) f[i]=i;
		for(int i=1;i<=2*n;i++) c[i].l=0x3f3f3f3f; 
		point=n;
		for(int i=1;i<=m;i++)
		{
			cin>>a[i].st>>a[i].en>>a[i].l>>a[i].h;
			insert2(a[i].st,a[i].en,a[i].l,a[i].h);
			insert2(a[i].en,a[i].st,a[i].l,a[i].h);
		}
		sort(a+1,a+m+1,cmp);
		dij(1);
		EX_kruskal();
		dfs(point,0);
		cin>>q>>k>>s;
		for(int i=1;i<=q;i++)
		{
			cin>>v>>p;
			v=(v+k*lastans-1)%n+1;
			p=(p+k*lastans)%(s+1);
			lastans=query(v,p);
			cout<<lastans<<endl;
		}
	}
	return 0;
}