$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} dist(v, d) + \sum_{i = l}^{r - 1} (A_i + k) 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