有一个由 $N$ 个顶点组成的树。顶点编号为 $0$ 到 $N-1$。另外，给定一个长度为 $N$ 的整数序列 $A_0, A_1, \ldots, A_{N - 1}$。

对于满足 $0 \le l < r \le N$ 的整数 $l, r$，以及顶点 $v, d$ 和非负整数 $k$，定义 $f(l, r, v, d, k) = 10^{-999999999} \cdot dist(v, d) + \sum_{i = l}^{r - 1} (A_i + k) \cdot dist(v, i)$，其中 $dist(a, b)$ 是连接顶点 $a$ 和 $b$ 的最短路径的长度。

需要执行如下查询：

• l r d k：输出使 $f(l, r, v, d, k)$ 最小的顶点 $v$。可以证明这样的 $v$ 是唯一的。

注意查询是在线给出的。详见输入部分。

输入格式

第一行给出树的大小 $N$。（$1 \le N \le 150{,}000$）

接下来 $N-1$ 行每行给出两个整数 $u, v$，表示存在连接顶点 $u, v$ 的边。（$0 \le u, v \le N-1$）

接下来一行给出序列 $A_0, A_1, \ldots, A_{N-1}$。（$0 \le A_i \le 150{,}000$）

接下来一行给出查询个数 $Q$。（$1 \le Q \le 150{,}000$）

接下来 $Q$ 行每行给出四个整数 $a, b, z, d$。（$0 \le a, b, d \le N - 1, 0 \le z \le 150{,}000$）

设 $X_i$ 为第 $i$ 个查询的答案（$0 \le i \le Q - 1$）。对于第 $i$ 个查询，$l, r, k$ 按以下公式恢复。$d$ 直接使用输入中给出的值。

• $a^\prime = (a + \sum_{j = 0}^{i - 1} X_j) \text{ mod } N$
• $b^\prime = (b + 2 \sum_{j = 0}^{i - 1} X_j) \text{ mod } N$
• $k = (z + (\sum_{j = 0}^{i - 1} X_j)^2) \text{ mod } 150\,001$
• $l = \min(a^\prime, b^\prime)$
• $r = 1 + \max(a^\prime, b^\prime)$

输出格式

共 $Q$ 行，每行输出问题的答案。

样例

输入格式 1

5
0 1
1 3
3 2
3 4
1000 10 1 100 10000
15
0 0 0 0
0 1 150000 1
2 0 0 2
3 0 150000 3
4 2 150000 4
1 1 149975 0
0 0 149965 1
1 2 149951 2
1 4 149901 3
3 4 149804 4
2 0 149745 0
3 1 149639 1
1 4 149517 2
4 3 149375 3
0 1 149160 4

输出格式 1

0
0
0
1
4
1
1
3
4
2
3
3
3
4
4