Mamy drzewo składające się z $N$ wierzchołków. Wierzchołki są ponumerowane od $1$ do $N$, a w $i$-tym wierzchołku przechowywana jest liczba całkowita $A_i$. Początkowo $A_i = 0$ dla $1 \le i \le N$.

Należy wykonać łącznie $Q$ zapytań następujących typów:

• 1 u v: Gdy korzeniem drzewa jest wierzchołek $u$, zwiększ o $1$ wartości $A_i$ dla wszystkich wierzchołków $i$ w poddrzewie o korzeniu w $v$.
• 2 u v: Zwiększ o $1$ wartości $A_i$ dla wszystkich wierzchołków $i$ na jedynej ścieżce między wierzchołkami $u$ a $v$.
• 3 v: Wypisz $\sum_{i=1}^{N} A_i \times dist(v, i)$, gdzie $dist(x, y)$ oznacza liczbę krawędzi na ścieżce między wierzchołkami $x$ a $y$.

Wejście

Pierwszy wiersz zawiera $N$ ($1 \le N \le 200\,000$).

Następne $N-1$ wierszy zawiera krawędzie drzewa. Każdy wiersz zawiera dwie liczby $u$ i $v$ oddzielone spacją, oznaczające krawędź łączącą $u$ i $v$ ($1 \le u, v \le N$).

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

Następne $Q$ wierszy zawiera zapytania, każde w jednym z następujących formatów:

• 1 u v ($1 \le u, v \le N$)
• 2 u v ($1 \le u, v \le N$)
• 3 v ($1 \le v \le N$)

Zapytania typu 3 występują co najmniej raz.

Wyjście

Dla każdego zapytania typu 3 wypisz wynik w osobnym wierszu, w kolejności występowania.

Przykład

Wejście

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
5