Il y a un arbre composé de $N$ sommets. Les sommets sont numérotés de $1$ à $N$, et chaque sommet $i$ contient un entier $A_i$. Initialement, $A_i = 0$. ($1 \le i \le N$)

Vous devez effectuer un total de $Q$ requêtes comme suit :

• 1 u v : Lorsque la racine de l'arbre est le sommet $u$, ajouter 1 à $A_i$ pour tous les sommets $i$ du sous-arbre enraciné en $v$.
• 2 u v : Ajouter 1 à $A_i$ pour tous les sommets $i$ sur le chemin unique entre les sommets $u$ et $v$.
• 3 v : Afficher $\sum_{i = 1}^{N} A_i \times dist(v, i)$. $dist(x, y)$ désigne le nombre d'arêtes sur le chemin entre les sommets $x$ et $y$.

Entrée

La première ligne contient $N$. ($1 \le N \le 200\,000$)

Les $N-1$ lignes suivantes décrivent les arêtes de l'arbre. Chaque ligne contient deux entiers $u$ et $v$ séparés par un espace, indiquant une arête entre $u$ et $v$. ($1 \le u, v \le N$)

La ligne suivante contient le nombre de requêtes $Q$. ($1 \le Q \le 200\,000$)

Les $Q$ lignes suivantes contiennent chacune une requête parmi les formats suivants :

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

Les requêtes de type 3 apparaissent au moins une fois.

Sortie

Pour chaque requête de type 3, afficher le résultat sur une ligne distincte, dans l'ordre.

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