#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
const int N = 2e5 + 7;
const int M = 4e5 + 7;
const int J = 30;
int T;
int n, m;
int q, k, s;
int last;
class edge {
	public:
		int tail;
		int head;
		int length;
		int height;
};
class S {
	public:
		int id;
		int dis;
		friend bool operator < (S x, S y) {
			return x.dis < y.dis;
		}
		friend bool operator > (S x, S y) {
			return x.dis > y.dis;
		}
};
edge e[M];
int temp;
int nex[M], head[N], len[M], hei[M], to[M];
int cnt;
bool vis[N];
int lch[N << 1], rch[N << 1];
int wei[N << 1];
unsigned int minleaf[N << 1];
int fas[N << 1];
int fak[J][N << 1], dep[N << 1];
int logn[N << 1];
bool greater_hei(edge x, edge y) {
	return x.height > y.height;
}
void add(int u, int v, int l, int a) { //链式前向星的加边 
	nex[++cnt] = head[u];
	to[cnt] = v;
	len[cnt] = l;
	hei[cnt] = a;
	head[u] = cnt;
}
void dijkstra() {
	std::memset(minleaf + 1, 0x3f, n * sizeof(int));
	std::memset(vis + 1, false, n * sizeof(bool));
	std::priority_queue <S, std::vector <S>, std::greater<S> > qu; 
	minleaf[1] = 0;
	qu.push((S){1, 0});
	while(!qu.empty()) {
		int u = qu.top().id;
		qu.pop();
		if(vis[u])
			continue;
		vis[u] = true;
		for(int i = head[u]; i; i = nex[i]) {
			int v = to[i];
			int w = len[i];
			if(minleaf[v] > minleaf[u] + w) {
				minleaf[v] = minleaf[u] + w;
				qu.push((S){v, minleaf[v]});
			}
		}
	}
}
int find(int x) {
	return x == fas[x] ? x : (fas[x] = find(fas[x]));
}
void kruskal() {
	std::sort(e, e + m, greater_hei);
	for(int i = 0; i < m; i++) {
		int u = e[i].tail;
		int v = e[i].head;
		int w = e[i].height;
		u = find(u);
		v = find(v);
		if(u != v) {
			cnt++;
			lch[cnt] = u;
			rch[cnt] = v;
			wei[cnt] = w;
			fas[u] = cnt;
			fas[v] = cnt;
			minleaf[cnt] = std::min(minleaf[u], minleaf[v]);
		}
	}
}
void init(int u, int f) {
	dep[u] = dep[f] + 1;
	fak[0][u] = f;
	for(int i = 1; i <= logn[dep[u]]; i++)
		fak[i][u] = fak[i - 1][fak[i - 1][u]];
	if(lch[u] != 0) init(lch[u], u);
	if(rch[u] != 0) init(rch[u], u);
}
int cal(int v, int p) {
	for(int i = logn[dep[v]]; i >= 0; i--)
		if(wei[fak[i][v]] > p) v = fak[i][v]; 
	return minleaf[v];
}
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	logn[1] = 0;
	for(int i = 2; i < N << 1; i++)
		logn[i] = logn[i / 2] + 1;
	std::cin >> T;
	while(T--) {
		temp = 0;
		std::memset(nex + 1, 0, m * sizeof(int));
		std::memset(head + 1, 0, n * sizeof(int));
		std::memset(lch + 1, 0, (2 * n + 1) * sizeof(int));
		std::memset(rch + 1, 0, (2 * n + 1) * sizeof(int));
		dep[0] = 0;
		std::cin >> n >> m;
		int u, v, l, a;
		for(int i = 0; i < m; i++) {
			std::cin >> u >> v >> l >> a;
			e[temp++] = (edge){u, v, l, a};
			add(u, v, l, a);
			add(v, u, l, a);
		}
		for(int i = 1; i <= 2 * n + 1; i++)
			fas[i] = i;
		dijkstra();
		cnt = n;
		kruskal();
		init(cnt, 0);
		std::cin >> q >> k >> s;
		for(int i = 0; i < q; i++) {
			int vv, pp, v, p;
			std::cin >> vv >> pp;
			v = (vv + k * last - 1) % n + 1;
			p = (pp + k * last) % (s + 1);
			last = cal(v, p);
			std::cout << last << '\n';
		}
	}
	return 0;
}

测试目录