Busy Beaver aime les problèmes de structures de données, mais il trouve que les problèmes de structures de données sur des tableaux avec des requêtes d'intervalle sont ennuyeux. Il a donc imaginé un autre type de problème de structure de données, avec des multiensembles !

Il existe une séquence $a_1, \dots, a_L$, où chaque $a_i$ est un multiensemble d'entiers positifs. Initialement, la séquence est vide, c'est-à-dire $L=0$. Implémentez les opérations suivantes :

• 1 M K : Ajouter un multiensemble composé uniquement du nombre $M$ apparaissant $K$ fois à la fin de la séquence.
• 2 X Y : Ajouter la somme de $a_X$ et $a_Y$ à la fin de la séquence. Le nombre d'occurrences de chaque valeur s'additionne ; par exemple, nous définissons la somme des multiensembles $\{1, 1, 2\}$ et $\{1, 2\}$ comme étant $\{1, 1, 1, 2, 2\}$.
• 3 X M K : Ajouter $f(a_X,M,K)$ à la fin de la séquence, où $f(S,M,K)$ est formé en supprimant $K$ copies de $M$ de $S$ si $S$ contient au moins $K$ copies de $M$, ou en ajoutant $K$ copies de $M$ à $S$ si $S$ contient strictement moins de $K$ copies de $M$.
• 4 X : Il est garanti que $a_X$ consiste en un seul élément. Affichez cet élément unique de $a_X$.

Entrée

La première ligne de l'entrée contient un entier unique $Q$ ($1 \le Q \le 5 \cdot 10^5$), le nombre d'opérations.

Les $Q$ lignes suivantes contiennent chacune une opération.

Il est garanti que :

• Les indices $X$ et $Y$ utilisés dans les opérations $2$, $3$ et $4$ restent toujours dans la séquence au moment de l'opération.
• Les valeurs $M$ et $K$ utilisées dans les opérations $1$ et $3$ satisfont $1 \le M,K \le 10^9$.
• Pour toutes les opérations de type $4$, $a_X$ contient exactement un élément.

Sortie

Pour chaque opération de type $4$, affichez une ligne contenant la réponse.

Sous-tâches

• ($10$ points) $1 \le M \le 10$ pour toutes les opérations de type $1$ et $3$.
• ($40$ points) Il est garanti que dans chaque opération de type $3$, le multiensemble nouvellement ajouté est formé en supprimant $K$ copies de $M$ de $a_X$.
• ($50$ points) Aucune contrainte supplémentaire.

Exemples

Entrée 1

8
1 5 1
1 6 2
4 1
2 1 2
3 3 6 4
3 4 6 5
3 5 5 1
4 6

Sortie 1

5
6

Remarque

Les multiensembles sont les suivants :

• $a_1 = \{5\}$.
• $a_2 = \{6, 6\}$.
• $a_3 = \{5, 6, 6\}$.
• $a_4 = \{5, 6, 6, 6, 6, 6, 6\}$.
• $a_5 = \{5, 6\}$.
• $a_6 = \{6\}$.