Masz drzewo o $N$ wierzchołkach. Wierzchołki są ponumerowane kolejnymi liczbami całkowitymi od $1$ do $N$, a $i$-ty wierzchołek zawiera zmienną $A_i$. Początkowo $A_i = 0$ ($1 \le i \le N$).

Musisz przetworzyć $Q$ zapytań. Każde zapytanie jest jednego z następujących typów:

• "1 $u$ $v$": Ustaw korzeń drzewa w wierzchołku $u$, rozważ poddrzewo wierzchołka $v$ i dla każdego wierzchołka $i$ w poddrzewie $v$ zwiększ $A_i$ o jeden.
• "2 $u$ $v$": Dla każdego wierzchołka $i$ na jedynej ścieżce prostej od $u$ do $v$ zwiększ $A_i$ o jeden.
• "3 $v$": Wypisz $\sum_{i=1}^{N} \text{dist}(v, i) \cdot A_i$, gdzie $\text{dist}(x, y)$ to liczba krawędzi na ścieżce od wierzchołka $x$ do wierzchołka $y$.

Wejście

Pierwsza linia zawiera liczbę całkowitą $N$, liczbę wierzchołków ($1 \le N \le 2 \cdot 10^5$).

Następne $N - 1$ linii zawiera opis drzewa. Każda z tych linii zawiera dwie liczby całkowite $u$ i $v$ oddzielone spacją, co oznacza, że istnieje krawędź łącząca $u$ i $v$ ($1 \le u, v \le N$). Gwarantuje się, że wynikowy graf jest drzewem.

Następna linia zawiera liczbę całkowitą $Q$, liczbę zapytań ($1 \le Q \le 2 \cdot 10^5$).

Następne $Q$ linii zawiera zapytania, po jednym w linii. Każde zapytanie jest podane w jednym z formatów opisanych powyżej ($1 \le u, v \le N$). Możesz założyć, że wystąpi co najmniej jedno zapytanie typu "3".

Wyjście

Dla każdego zapytania typu "3" wypisz wynik w osobnej linii.

Przykład

Wejście 1

5
4 2
2 5
1 5
1 3
5
2 2 4
3 4
2 1 5
2 5 5
3 2

Wyjście 1

1
5