Mamy drzewo składające się z $N$ wierzchołków. Wierzchołki są ponumerowane od $0$ do $N-1$. Dodatkowo dany jest ciąg liczb całkowitych $A_0, A_1, \ldots, A_{N-1}$ długości $N$.

Niech $0 \le l < r \le N$ będą liczbami całkowitymi, a $v, d$ oraz $k$ będzie nieujemną liczbą całkowitą. Definiujemy $f(l, r, v, d, k) = 10^{-999999999} dist(v, d) + \sum_{i = l}^{r - 1} (A_i + k) dist(v, i)$, gdzie $dist(a, b)$ jest długością najkrótszej ścieżki między wierzchołkami $a$ i $b$.

Należy obsłużyć następujące zapytania:

• l r d k: Wypisz $v$, które minimalizuje $f(l, r, v, d, k)$. Można wykazać, że takie $v$ jest jedyne.

Zapytania są podawane online. Szczegóły w części Wejście.

Wejście

Pierwszy wiersz zawiera rozmiar drzewa $N$. ($1 \le N \le 150\,000$)

Następne $N-1$ wierszy zawiera dwie liczby całkowite $u, v$, oznaczające krawędź między wierzchołkami $u$ i $v$. ($0 \le u, v \le N-1$)

Następny wiersz zawiera ciąg $A_0, A_1, \ldots, A_{N-1}$. ($0 \le A_i \le 150\,000$)

Następny wiersz zawiera liczbę zapytań $Q$. ($1 \le Q \le 150\,000$)

Następne $Q$ wierszy zawiera cztery liczby całkowite $a, b, z, d$. ($0 \le a, b, d \le N-1$, $0 \le z \le 150\,000$)

Niech $X_i$ będzie odpowiedzią na $i$-te zapytanie ($0 \le i \le Q-1$). Dla $i$-tego zapytania wartości $l, r, k$ są odtwarzane według poniższych wzorów. $d$ jest podane bezpośrednio w wejściu.

• $a^\prime = (a + \sum_{j = 0}^{i - 1} X_j) \bmod N$
• $b^\prime = (b + 2\sum_{j = 0}^{i - 1} X_j) \bmod N$
• $k = (z + (\sum_{j = 0}^{i - 1} X_j)^2) \bmod 150\,001$
• $l = \min(a^\prime, b^\prime)$
• $r = 1 + \max(a^\prime, b^\prime)$

Wyjście

Wypisz $Q$ wierszy, każdy zawierający odpowiedź na odpowiednie zapytanie.

Przykład

Wejście

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

Wyjście

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