Hay un árbol con $N$ vértices. Los vértices están numerados del $1$ al $N$, y el vértice $i$ tiene un entero $A_i$ almacenado. Inicialmente, $A_i = 0$. ($1 \le i \le N$)

Debes realizar $Q$ consultas de los siguientes tipos:

• 1 u v: Cuando la raíz del árbol es el vértice $u$, suma $1$ a $A_i$ de todos los vértices $i$ en el subárbol con raíz en $v$.
• 2 u v: Suma $1$ a $A_i$ de todos los vértices $i$ en el camino único entre los vértices $u$ y $v$.
• 3 v: Imprime $\sum_{i = 1}^{N} A_i \times dist(v, i)$. $dist(x, y)$ es el número de aristas en el camino entre $x$ e $y$.

Entrada

La primera línea contiene $N$. ($1 \le N \le 200\,000$)

Las siguientes $N-1$ líneas contienen las aristas del árbol. Cada línea contiene dos números $u$ y $v$ separados por un espacio, que indican que hay una arista entre $u$ y $v$. ($1 \le u, v \le N$)

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

Las siguientes $Q$ líneas contienen una consulta por línea con uno de los siguientes formatos:

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

La consulta de tipo 3 aparece al menos una vez.

Salida

Para cada consulta de tipo 3, imprime el resultado en una línea por orden de aparición.

Ejemplos

Entrada

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

Salida

1
5