Tienes un árbol de $N$ vértices. Los vértices están enumerados con enteros secuenciales del 1 al $N$, y el $i$-ésimo vértice contiene la variable $A_i$. Inicialmente $A_i = 0$ ($1 \le i \le N$).

Debes procesar $Q$ consultas. Cada consulta es una de las siguientes:

• "1 $u$ $v$": Enraíza el árbol en el vértice $u$, considera el subárbol del vértice $v$, y para cada vértice $i$ en el subárbol de $v$, aumenta $A_i$ en uno.
• "2 $u$ $v$": Para cada vértice $i$ en el camino simple único desde $u$ hasta $v$, aumenta $A_i$ en uno.
• "3 $v$": Imprime $\sum_{i=1}^{N} \text{dist}(v, i) \cdot A_i$, donde $\text{dist}(x, y)$ es el número de aristas en el camino desde el vértice $x$ hasta el vértice $y$.

Entrada

La primera línea contiene un entero $N$, el número de vértices ($1 \le N \le 2 \cdot 10^5$).

Las siguientes $N - 1$ líneas contienen la descripción del árbol. Cada una de estas líneas contiene dos enteros $u$ y $v$ separados por un espacio, lo que significa que hay una arista que conecta $u$ y $v$ ($1 \le u, v \le N$). Se garantiza que el grafo resultante es un árbol.

La siguiente línea contiene un entero $Q$, el número de consultas ($1 \le Q \le 2 \cdot 10^5$).

Las siguientes $Q$ líneas contienen las consultas, una por línea. Cada consulta se proporciona en uno de los formatos descritos anteriormente ($1 \le u, v \le N$). Puedes asumir que hay al menos una consulta de tipo "3".

Salida

Para cada consulta de tipo "3", imprime el resultado en una línea separada.

Ejemplos

Entrada 1

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

1
5