Problem Statement

First, you are given a tree with $N$ vertices. The vertices are numbered from $0$ to $N-1$. There are $N-1$ edges, and the $i$-th edge ( $0\leq i\leq N-2$ ) connects vertices $u_i$ and $v_i$. For $2$ vertices $u$ , $v$ of the given tree, let $\text{dist}(u,v)$ denote the number of edges on the shortest path between $u$ , $v$. When $u=v$, $\text{dist}(u,v)=0$. Furthermore, you are given a sequence $(A_0,A_1,\ldots ,A_{N-1})$.

For integers $l$, $r$ satisfying $0\leq l\lt r\leq N$, a vertex $v$, a vertex $\delta$, and a non-negative integer $k$, define $f(l,r,v,\delta ,k)=10^{-100}\text{dist}(v,\delta )+\sum_{w=l}^{r-1} (A_w+k)\text{dist}(v,w)$.

You are given $Q$ queries. In the $i$-th query $(0\leq i \leq Q-1)$, for the given non-negative integers $l_i$ , $r_i$ , ${\delta}_i$ , $k_i$, find the number of the vertex $v$ that minimizes the value of $f(l_i,r_i,v,{\delta}_i,k_i)$. Under the constraints of this problem, such a $v$ is unique. Let $X_i$ be the answer to the $i$-th query.

Actually, in the $i$-th query, you are given ${a^{\prime}}_i$ , ${b^{\prime}}_i$ , ${k^{\prime}}_i$ instead of $l_i$ , $r_i$ , $k_i$, so restore them using the answers to the previous queries by the following procedure.

1. If $i=0$, let $a_i={a^{\prime}}_i$; if $i\neq 0$, let $a_i=\left( {a^{\prime}}_i+\sum_{j=0}^{i-1}X_j\right) \bmod N$.
2. If $i=0$, let $b_i={b^{\prime}}_i$; if $i\neq 0$, let $b_i=\left( {b^{\prime}}_i+2\sum_{j=0}^{i-1}X_j\right) \bmod N$.
3. If $i=0$, let $k_i={k^{\prime}}_i$; if $i\neq 0$, let $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$

Note that $150\ 001$ is a prime number.

Constraints

The input satisfies the following constraints.

• $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$
• The graph formed by the given edges is a tree
• $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$
• All input values are integers

It is also guaranteed that the restored $l_i$ , $r_i$ , $k_i$ satisfy the following constraints.

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

Input

The input is given in the following format.

$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}$

Output

$X_0$
$X_1$
$\vdots$
$X_{Q-1}$

Sample

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