Description：

一个无向连通图，每条边有长度和海拔，多次询问从 $p$ 开始只经过海拔不超过 $v$ 的边所能到达的点中距 $1$ 号点最近的距离。

$1\leqslant n,q\leqslant 200000,1\leqslant m\leqslant 400000$

Solution：

首先如果可以离线的话那么可以把边和询问排序然后依次把边加入，用并查集动态统计联通块最小值。

但是本题强制在线，一个做法是把并查集可持久化，然后和上面一样做。

但是有更优秀的解法，就是利用 $kruskal$ 重构树，把边按海拔从高到低排序，建立 $kruskal$ 重构树，那么从一个点开始只经过海拔不超过 $v$ 的边所能到达的点是重构树的一棵子树，并且从这个点向上爬限制越来越紧，于是倍增找到限制最近的一个点，预处理一个子树最小值即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

#define R register

inline int rd()

{

	R int res = 0,f = 1;

	R char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int n,m;

int q,w,s;

#define MAXN 400010

#define MAXM 400010

struct edges

{

	int u,v,l,h;

}es[MAXM];

bool cmp_h(edges a,edges b){return a.h > b.h;}

int d[MAXN];

namespace Dij{

	struct edge

	{

		int to,nxt,v;

	}e[MAXM << 1];

	int edgenum = 0;

	int lin[MAXN] = {0};

	void add(int a,int b,int c)

	{

		e[++edgenum] = (edge){b,lin[a],c};lin[a] = edgenum;

		e[++edgenum] = (edge){a,lin[b],c};lin[b] = edgenum;

		return;

	}

	bool v[MAXN];

	void init()

	{

		memset(v,false,sizeof(v));

		edgenum = 0;

		memset(lin,0,sizeof(lin));

		return;

	}

	void dij()

	{

		priority_queue< pair<int,int> > q;

		q.push(make_pair(0,1));

		memset(d,0x3f,sizeof(d));d[1] = 0;

		while(!q.empty())

		{

			int k = q.top().second;q.pop();

			if(v[k])continue;

			v[k] = true;

			for(int i = lin[k];i != 0;i = e[i].nxt)

			{

				if(d[e[i].to] > d[k] + e[i].v)

				{

					d[e[i].to] = d[k] + e[i].v;

					q.push(make_pair(-d[e[i].to],e[i].to));

				}

			}

		}

		return;

	}

}

namespace UFS{

	int f[MAXN];

	int find(int x){return (x == f[x] ? x : f[x] = find(f[x]));}

	void init()

	{

		for(int i = 1;i <= n;++i)f[i] = i;

		return;

	}

}

namespace Kruskal{

	struct edge

	{

		int to,nxt;

	}e[MAXN << 1];

	int edgenum = 0;

	int lin[MAXN] = {0};

	void add(int a,int b)

	{

		e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

		e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

		return;

	}

	int val[MAXN];

	bool v[MAXN];

	void init()

	{

		memset(val,0,sizeof(val));

		memset(v,false,sizeof(v));

		memset(lin,0,sizeof(lin));

		edgenum = 0;

		return;

	}

	void dfs(int k)

	{

		v[k] = true;

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			if(v[e[i].to])continue;

			dfs(e[i].to);

			d[k] = min(d[k],d[e[i].to]);

		}

		return;

	}

	int tot;

	void build()

	{

		sort(es + 1,es + 1 + m,cmp_h);

		tot = n;

		using namespace UFS;

		for(int i = 1;i <= m;++i)

		{

			int p = find(es[i].u),q = find(es[i].v);

			if(p == q)continue;

			++tot;f[p] = f[q] = f[tot] = tot;

			add(p,tot);add(q,tot);

			val[tot] = es[i].h;

		}

		dfs(tot);

		return;

	}

}

namespace Doubling{

	int f[MAXN][23],g[MAXN][23];

	using namespace Kruskal;

	int dep[MAXN];

	void init()

	{

		memset(f,0,sizeof(f));

		memset(g,0,sizeof(g));

		memset(dep,0,sizeof(dep));

		return;

	}

	void build()

	{

		memset(v,false,sizeof(v));

		queue<int> q;q.push(tot);

		dep[tot] = 1;

		while(!q.empty())

		{

			int k = q.front();q.pop();

			v[k] = true;

			for(int i = lin[k];i != 0;i = e[i].nxt)

			{

				if(v[e[i].to])continue;

				dep[e[i].to] = dep[k] + 1;

				f[e[i].to][0] = k;

				g[e[i].to][0] = val[k];

				q.push(e[i].to);

			}

		}

		for(int k = 1;k <= 22;++k)

		{

			for(int i = 1;i <= tot;++i)

			{

				g[i][k] = min(g[i][k - 1],g[f[i][k - 1]][k - 1]);

				f[i][k] = f[f[i][k - 1]][k - 1];

			}

		}

		return;

	}

	int calc(int k,int h)

	{

		int pos = k;

		for(int i = 22;i >= 0;--i)

		{

			if(f[pos][i] != 0 && g[pos][i] > h)

			{

				pos = f[pos][i];

			}

		}

		return pos;

	}

}

void clr()

{

	Dij::init();

	Kruskal::init();

	Doubling::init();

	return;

}

void work()

{

	clr();

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= m;++i)

	{

		es[i].u = rd();es[i].v = rd();

		es[i].l = rd();es[i].h = rd();

		Dij::add(es[i].u,es[i].v,es[i].l);

	}

	Dij::dij();

	UFS::init();

	Kruskal::build();

	Doubling::build();

	scanf("%d%d%d",&q,&w,&s);

	int p,h;

	int lastans = 0;

	for(int i = 1;i <= q;++i)

	{

		scanf("%d%d",&p,&h);

		p = (p + w * lastans - 1) % n + 1;

		h = (h + w * lastans) % (s + 1);

		printf("%d\n",lastans = d[Doubling::calc(p,h)]);

	}

	return;

}

int main()

{

	int testcases = rd();

	while(testcases--)work();

	return 0;

}