Vous disposez d'un arbre à $N$ sommets. Les sommets sont numérotés par des entiers séquentiels de $1$ à $N$, et le $i$-ième sommet contient la variable $A_i$. Initialement, $A_i = 0$ ($1 \le i \le N$).

Vous devez traiter $Q$ requêtes. Chaque requête est l'une des suivantes :

• "1 $u$ $v$" : Enraciner l'arbre au sommet $u$, considérer le sous-arbre du sommet $v$, et pour chaque sommet $i$ dans le sous-arbre de $v$, augmenter $A_i$ de un.
• "2 $u$ $v$" : Pour chaque sommet $i$ sur l'unique chemin simple allant de $u$ à $v$, augmenter $A_i$ de un.
• "3 $v$" : Afficher $\sum_{i=1}^{N} \text{dist}(v, i) \cdot A_i$, où $\text{dist}(x, y)$ est le nombre d'arêtes sur le chemin allant du sommet $x$ au sommet $y$.

Entrée

La première ligne contient un entier $N$, le nombre de sommets ($1 \le N \le 2 \cdot 10^5$).

Les $N - 1$ lignes suivantes contiennent la description de l'arbre. Chacune de ces lignes contient deux entiers $u$ et $v$ séparés par un espace, signifiant qu'il existe une arête reliant $u$ et $v$ ($1 \le u, v \le N$). Il est garanti que le graphe résultant est un arbre.

La ligne suivante contient un entier $Q$, le nombre de requêtes ($1 \le Q \le 2 \cdot 10^5$).

Les $Q$ lignes suivantes contiennent les requêtes, une par ligne. Chaque requête est donnée dans l'un des formats décrits ci-dessus ($1 \le u, v \le N$). Vous pouvez supposer qu'il y a au moins une requête de type "3".

Sortie

Pour chaque requête de type "3", affichez le résultat sur une ligne séparée.

Exemples

Entrée 1

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

Sortie 1

1
5