先跑一次dijkstra得到每个点到 \(1\) 的最短路
然后按海拔跑最大生成树得到kruskal重构树
那么一个点在能开车到的地方就是对应海拔高于 \(p\) 的最高的点的子树
然后取子树中dis的min即可
#include <bits/stdc++.h>
#define pii pair<int, int>
char buf[1 << 21], *p1 = buf, *p2 = buf;
inline char getc() {
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
}
inline int read() {
int x = 0, f = 1; char ch = getc();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getc(); }
while (ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getc(); }
return x * f;
}
inline bool chkmax(int &a, int b) { return a < b ? a = b, 1 : 0; }
inline bool chkmin(int &a, int b) { return a > b ? a = b, 1 : 0; }
const int N = 4e5 + 7;
const int INF = 0x3f3f3f3f;
struct Edge {
int u, v, a;
bool operator < (const Edge &p) const { return a > p.a; }
} edge[N];
int n, m, head[N], cnt = 1, ne[N * 2], to[N * 2], c[N * 2], dis[N];
bool done[N];
int pa[N], fa[N][21], alp[N];
inline int find(int x) { return x == pa[x] ? x : pa[x] = find(pa[x]); }
void add(int u, int v, int cc) {
to[++cnt] = v; ne[cnt] = head[u]; c[cnt] = cc; head[u] = cnt;
}
void dijkstra() {
for (int i = 1; i <= 2 * n; i++) dis[i] = INF, done[i] = 0;
dis[1] = 0;
std::priority_queue<std::pii, std::vector<std::pii>, std::greater<std::pii> > que;
que.push(std::pii(0, 1));
while (!que.empty()) {
int u = que.top().second; que.pop();
if (done[u]) continue;
done[u] = 1;
for (int i = head[u]; i; i = ne[i]) {
int v = to[i];
if (chkmin(dis[v], dis[u] + c[i]))
que.push(std::pii(dis[v], v)), assert(dis[v] == dis[u] + c[i]);
}
}
}
void kruskal() {
std::sort(edge, edge + m);
for (int i = 1; i <= 2 * n; i++) pa[i] = i;
int node = n;
for (int i = 0; i < m; i++) {
int u = find(edge[i].u), v = find(edge[i].v);
if (u == v) continue;
fa[u][0] = fa[v][0] = pa[u] = pa[v] = ++node;
dis[node] = std::min(dis[u], dis[v]);
alp[node] = edge[i].a;
}
for (int j = 1; j <= 20; j++)
for (int i = 1; i <= node; i++)
fa[i][j] = fa[fa[i][j - 1]][j - 1];
}
void solve() {
n = read(), m = read();
for (int i = 0; i < m; i++) {
int u = read(), v = read(), l = read(), a = read();
add(u, v, l); add(v, u, l);
edge[i].u = u, edge[i].v = v, edge[i].a = a;
}
dijkstra();
kruskal();
int Q = read(), K = read(), S = read();
alp[0] = -INF;
for (int u, p, ans = 0; Q--; ) {
u = read(), p = read();
u = (u + K * ans - 1) % n + 1;
p = (p + K * ans) % (S + 1);
for (int i = 20; ~i; i--) {
if (alp[fa[u][i]] > p)
u = fa[u][i];
}
assert(u);
printf("%d\n", ans = dis[u]);
}
cnt = 1;
for (int i = 1; i <= 2 * n; i++)
head[i] = 0, memset(fa[i], 0, sizeof(fa[i]));
}
int main() {
//freopen("ans.out", "w", stdout);
int T = read();
while (T--) solve();
}