Hay un árbol formado por $N$ vértices. Los vértices están numerados del $0$ al $N-1$. Además, se da una secuencia de enteros $A_0, A_1, \ldots, A_{N - 1}$ de longitud $N$.

Para enteros $l, r$ que satisfacen $0 \le l < r \le N$, un vértice $v, d$ y un entero no negativo $k$, definimos $f(l, r, v, d, k) = 10^{-999999999} dist(v, d) + \sum_{i = l}^{r - 1} (A_i + k) dist(v, i)$, donde $dist(a, b)$ es la longitud del camino más corto entre los dos vértices $a$ y $b$.

Se deben realizar las siguientes consultas:

• l r d k: Imprime el $v$ que minimiza $f(l, r, v, d, k)$. Se puede demostrar que dicho $v$ es único.

Ten en cuenta que las consultas se dan en línea. Para más detalles, consulta la sección de entrada.

Entrada

La primera línea contiene el tamaño del árbol $N$ ($1 \le N \le 150{,}000$).

Las siguientes $N-1$ líneas contienen dos enteros $u, v$, lo que significa que existe una arista que conecta los dos vértices $u$ y $v$ ($0 \le u, v \le N-1$).

La siguiente línea contiene la secuencia $A_0, A_1, \ldots, A_{n-1}$ ($0 \le A_i \le 150{,}000$).

La siguiente línea contiene el número de consultas $Q$ ($1 \le Q \le 150{,}000$).

Las siguientes $Q$ líneas contienen cuatro enteros $a, b, z, d$ ($0 \le a, b, d \le n - 1$, $0 \le z \le 150{,}000$).

Sea $X_i$ la respuesta a la $i$-ésima consulta ($0 \le i \le Q - 1$). Para la $i$-ésima consulta, $l, r, k$ se pueden recuperar mediante las siguientes fórmulas. $d$ se usa tal como se da en la entrada.

• $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)$

Salida

Imprime $Q$ líneas con las respuestas al problema.

Ejemplos

Entrada

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

Salida

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