問題文

まず、 $N$ 頂点の木が与えられます。頂点には $0$ から $N-1$ まで番号が付けられています。 辺は $N-1$ 個ありますが、 $i$ 番目の辺（ $0\leq i\leq N-2$ ）は頂点 $u_i$ と頂点 $v_i$ を結びます。 与えられた木の $2$ 頂点 $u$ , $v$ に対して、 $u$ , $v$ 間の最短パスに含まれる辺の個数を $\text{dist}(u,v)$ と表します。 $u=v$ のときは $\text{dist}(u,v)=0$ です。 さらに、数列 $(A_0,A_1,\ldots ,A_{N-1})$ が与えられます。

$0\leq l\lt r\leq N$ を満たす整数 $l$, $r$ と頂点 $v$ 、頂点 $\delta$ 、非負整数 $k$ に関して $f(l,r,v,\delta ,k)=10^{-100}\text{dist}(v,\delta )+\sum_{w=l}^{r-1} (A_w+k)\text{dist}(v,w)$ と定義します。

ここで、 $Q$ 個のクエリが与えられます。 $i$ 番目のクエリ $(0\leq i \leq Q-1)$ では与えられる非負整数 $l_i$ , $r_i$ , ${\delta}_i$ , $k_i$ に対して、 $f(l_i,r_i,v,{\delta}_i,k_i)$ の値を最小化するような $v$ の番号を求めてください。そのような $v$ はこの問題の制約のもとで一意です。 $i$ 番目のクエリの答えを $X_i$ とします。

実際には、 $i$ 番目のクエリでは $l_i$ , $r_i$ , $k_i$ の代わりに ${a^{\prime}}_i$ , ${b^{\prime}}_i$ , ${k^{\prime}}_i$ が与えられるので、それ以前のクエリの答えを用いて次の手順で復元してください。

1. $i=0$ のときは $a_i={a^{\prime}}_i$ 、 $i\neq 0$ のときは $a_i=\left( {a^{\prime}}_i+\sum_{j=0}^{i-1}X_j\right) \bmod N$ とする。
2. $i=0$ のときは $b_i={b^{\prime}}_i$ 、 $i\neq 0$ のときは $b_i=\left( {b^{\prime}}_i+2\sum_{j=0}^{i-1}X_j\right) \bmod N$ とする。
3. $i=0$ のときは $k_i={k^{\prime}}_i$ 、 $i\neq 0$ のときは $k_i=\left( {k^{\prime}}_i+\left(\sum_{j=0}^{i-1}X_j\right)^2\right)\bmod 150\ 001$ とする。
4. $l_i=\min\lbrace a_i, b_i \rbrace$
5. $r_i=1+\max\lbrace a_i, b_i \rbrace$

ちなみに、 $150\ 001$ は素数です。

制約

入力は次の制約を満たします。

• $1\leq N \leq 150\ 000$
• $1\leq Q \leq 150\ 000$
• $0\leq u_i\leq N-1$
• $0\leq v_i\leq N-1$
• 与えられた辺からなるグラフは木である
• $0\leq A_i\leq 150\ 000$
• $0\leq {a^{\prime}}_i\lt N$
• $0\leq {b^{\prime}}_i\lt N$
• $0\leq {k^{\prime}}_i\leq 150\ 000$
• $0\leq \delta_i\lt N$
• 入力はすべて整数

また、復元された $l_i$ , $r_i$ , $k_i$ は次の制約を満たすことが保証されます。

• $0\leq l_i\lt r_i\leq N$
• $0\leq k_i\leq 150\ 000$

入力

入力は次の形式で与えられます。

$N$
$u_0$ $v_0$
$u_1$ $v_1$
$\vdots$
$u_{N-2}$ $v_{N-2}$
$A_0$ $A_1$ $\ldots$ $A_{N-1}$
$Q$
${a^{\prime}}_0$ ${b^{\prime}}_0$ ${k^{\prime}}_0$ $\delta_0$
${a^{\prime}}_1$ ${b^{\prime}}_1$ ${k^{\prime}}_1$ $\delta_1$
$\vdots$
${a^{\prime}}_{Q-1}$ ${b^{\prime}}_{Q-1}$ ${k^{\prime}}_{Q-1}$ $\delta_{Q-1}$

出力

$X_0$
$X_1$
$\vdots$
$X_{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

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

5
0 1
1 3
3 2
3 4
1000 10 1 100 10000
15
0 1 0 0
0 2 150000 1
0 3 0 2
0 4 150000 3
0 5 0 4
1 2 150000 0
1 3 0 1
1 4 150000 2
1 5 0 3
2 3 150000 4
2 4 0 0
2 5 150000 1
3 4 0 2
3 5 150000 3
4 5 0 4