# Description
洛谷传送门
# Solution
重构树好题。
我们先按照水位 ，建 重构树。具体来讲：按水位从高到低排序，每次选出剩余边中水位最高的一条边插入到树中，这样就建成了一个小根堆。
然后我们再来考虑询问。
对于一个水位线 ，若 重构树上的点 的水位，那么在以 为根的子树中，开车是可以随意通行的，对答案没有贡献。
若 且 ，那么它就不得不在点 下车，所以对答案的贡献就是从 到 1 的距离。
那这个距离该如何算呢？
这个很简单，只需要提前跑个 堆优化预处理一下即可，千万千万千万不要使用 （spfa 就是在这里死的 QwQ）
我们对于一组询问 ，找到上述的 节点即可。
现在的问题就是如何找到这样的节点，我们考虑倍增，倍增向上跳（就是个板子），具体见代码。
# Code
（UOJ 不干人事 hack 了 把 0x3f3f3f3f 作为无穷大，而且无穷大开 的话还得开 ，所以这里放个洛谷能过的代码吧。）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
using namespace std;
namespace IO{
inline int read(){
int x = 0;
char ch = getchar();
while(!isdigit(ch)) ch = getchar();
while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
return x;
}
template <typename T> inline void write(T x){
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
}
using namespace IO;
const int N = 4e5 + 10;
int T, n, m, lst;
struct node{
int u, v, l, a, nxt;
bool operator < (const node &b) const{
return a > b.a;
}
}edge[N << 1], e[N << 1], tmp[N << 1];
int head[N], tot;
inline void add(int x, int y, int l){
edge[++tot].v = y, edge[tot].l = l, edge[tot].nxt = head[x];
head[x] = tot;
}
struct Heap{
int id, dis;
bool operator < (const Heap &b) const{
return dis > b.dis;
}
};
int dis[N];
inline void dijkstra(){
priority_queue <Heap> q;
q.push((Heap){1, 0});
memset(dis, 0x3f, sizeof(dis));
dis[1] = 0;
while(!q.empty()){
Heap now = q.top();
q.pop();
int x = now.id;
if(dis[x] < now.dis) continue;
for(int i = head[x]; i; i = edge[i].nxt){
int y = edge[i].v;
if(dis[y] > dis[x] + edge[i].l){
dis[y] = dis[x] + edge[i].l;
q.push((Heap){y, dis[y]});
}
}
}
}
int f[N];
int cnt;
vector <int> g[N];
inline int find(int x){
return f[x] == x ? x : f[x] = find(f[x]);
}
inline void kruskal(){
sort(e + 1, e + 1 + m);
for(int i = 1; i <= n; ++i) f[i] = i;
cnt = n;
int num = 0;
for(int i = 1; i <= m; ++i){
int fu = find(e[i].u), fv = find(e[i].v);
if(fu != fv){
num++;
tmp[++cnt].a = e[i].a;
f[fu] = f[fv] = f[cnt] = cnt;
g[cnt].push_back(fu), g[cnt].push_back(fv);
}
if(num == n - 1) break;
}
}
int fa[N][20], dep[N];
inline void dfs(int x, int p){
fa[x][0] = p, dep[x] = dep[p] + 1;
for(int i = 1; i <= 19; ++i) fa[x][i] = fa[fa[x][i - 1]][i - 1];
for(auto y : g[x])
dfs(y, x), tmp[x].l = min(tmp[x].l, tmp[y].l);
}
inline int query(int x, int y){
for(int i = 19; i >= 0; --i)
if(dep[x] - (1 << i) > 0 && tmp[fa[x][i]].a > y)
x = fa[x][i];
return tmp[x].l;
}
inline void solve(){
kruskal();
dfs(cnt, 0);
int q = read(), k = read(), s = read();
while(q--){
int u = (read() + k * lst - 1) % n + 1, p = (read() + k * lst) % (s + 1);
write(lst = query(u, p)), puts("");
}
}
inline void clear(){
memset(head, 0, sizeof(head));
memset(fa, 0, sizeof(fa));
memset(tmp, 0, sizeof(tmp));
memset(f, 0, sizeof(f));
for(int i = 1; i <= cnt; ++i) g[i].clear();
tot = lst = 0;
}
int main(){
T = read();
while(T--){
n = read(), m = read();
for(int i = 1; i <= m; ++i){
e[i].u = read(), e[i].v = read(), e[i].l = read(), e[i].a = read();
add(e[i].u, e[i].v, e[i].l), add(e[i].v, e[i].u, e[i].l);
}
dijkstra();
for(int i = 1; i <= n; ++i) tmp[i].l = dis[i];
for(int i = (n + 1); i <= (n << 1); ++i) tmp[i].l = INF;
solve(), clear();
}
return 0;
}
