問題文

まず、 $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$ は素数です。

制約

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

• $N = 150\ 000$
• $Q = 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}$