#include <queue>
#include <cstdio>
#include <vector>
#include <algorithm>
#define int long long

using namespace std;
const int N = 2e5 + 5;
const int M = 4e5 + 5;

bool vis[N];
int v0, p0, v, p;
int f[N << 1][25];
int last, n, m, cnt, idx;
vector <pair <int, int> > mp[N];
int h[N << 1], e[M << 1], ne[M << 1];
int b[N << 1], d[N << 1], fa[N << 1], dep[N << 1];

struct fg
{
	int u, v, w, a;
} bi[N << 2];

inline void add(int a, int b)
{
	e[idx] = b;
	ne[idx] = h[a];
	h[a] = idx ++ ;
}

inline int find(int x)
{
	if(x == fa[x]) return x;
	return fa[x] = find(fa[x]);
}

inline bool cmp(fg x, fg y) {return x.a > y.a;}

inline void dij()
{
	priority_queue <pair <int, int>, vector <pair<int, int> >,greater <pair <int, int> > > q;
	q.push({0, 1});
	for(int i = 1; i <= n; ++ i) d[i] = 0x3f3f3f3f3f3f3f3f;
	d[1] = 0;
	while(!q.empty())
	{
		int dis = q.top().first, u = q.top().second;
		q.pop();
		if(vis[u]) continue;
		vis[u] = 1;
		for(int i = 0; i < mp[u].size(); ++ i)
		{
			int w = mp[u][i].first, j = mp[u][i].second;
			if(vis[j]) continue;
			if(d[j] > d[u] + w)
			{
				d[j] = d[u] + w;
				q.push({d[j], j});
			}
		}
	}
}

inline int dfs(int u, int la)
{
	dep[u] = dep[la] + 1;
	f[u][0] = la;
	for(int i = 1; i <= 19; ++ i)
		f[u][i] = f[f[u][i - 1]][i - 1];
	if(u <= n) return d[u];
	int ans = 1e9;
	for(int i = h[u]; ~i; i = ne[i])
	{
		int j = e[i];
		if(j == la) continue;
		ans = min(ans, dfs(j, u));
	}
	return d[u] = ans;
}

inline int LCA(int u)
{
	for(int i = 19; ~i; -- i)
		if(dep[u] - (1 << i) > 0 && b[f[u][i]] > p)
			u = f[u][i];
	return d[u];
}

signed main()
{
	int T; scanf("%lld", &T);
	while(T -- )
	{
		scanf("%lld%lld", &n, &m), cnt = n;
		idx = 0;
		for(int i = 1; i <= n << 1; ++ i)
			fa[i] = i, h[i] = -1, dep[i] = b[i] = 0;
		for(int i = 1; i <= n; ++ i)
			mp[i].clear(), vis[i] = 0;
		for(int i = 1; i <= n << 2; ++ i)
			e[i] = ne[i] = 0;
		for(int i = 1; i <= m; ++ i)
		{
			int u, v, w, a;
			scanf("%lld%lld%lld%lld", &u, &v, &w, &a);
			mp[u].push_back({w, v});
			mp[v].push_back({w, u});
			bi[i] = {u, v, w, a};
		}
		dij();
		
		sort(bi + 1, bi + m + 1, cmp);
		for(int i = 1; i <= m; ++ i)
		{
			int u = find(bi[i].u), v = find(bi[i].v);
			if(u != v)
			{
				cnt ++ , b[cnt] = bi[i].a;
				fa[u] = fa[v] = cnt;
				add(u, cnt), add(cnt, u);
				add(v, cnt), add(cnt, v);
			}
		}
		dep[0] = 0;
		dfs(cnt, 0);
		int q, k, s;
		
		scanf("%lld%lld%lld", &q, &k, &s);
		
		for(int i = 1; i <= q; ++ i)
		{
			scanf("%lld%lld", &v0, &p0);
			v = (v0 + k * last - 1) % n + 1;
			p = (p0 + k * last) % (s + 1);
			int ans = LCA(v);
			printf("%lld\n", ans);
			last = ans;
		}
	}
	return 0;
}

测评记录