A Busy Beaver le gustan los problemas de estructuras de datos, pero piensa que los problemas de estructuras de datos sobre arreglos con consultas de intervalo son aburridos. ¡Así que se le ocurrió un tipo diferente de problema de estructuras de datos, con multiconjuntos!

Existe una secuencia $a_1, \dots, a_L$, donde cada $a_i$ es un multiconjunto de enteros positivos. Inicialmente, la secuencia está vacía, es decir, $L=0$. Implemente las siguientes operaciones:

• 1 M K: Añadir un multiconjunto que consiste únicamente en el número $M$ apareciendo $K$ veces al final de la secuencia.
• 2 X Y: Añadir la suma de $a_X$ y $a_Y$ al final de la secuencia. El número de ocurrencias de cada valor se suma; por ejemplo, definimos la suma de los multiconjuntos $\{1, 1, 2\}$ y $\{1, 2\}$ como $\{1, 1, 1, 2, 2\}$.
• 3 X M K: Añadir $f(a_X,M,K)$ al final de la secuencia, donde $f(S,M,K)$ se forma eliminando $K$ copias de $M$ de $S$ si $S$ tiene al menos $K$ copias de $M$, o añadiendo $K$ copias de $M$ a $S$ si $S$ tiene estrictamente menos de $K$ copias de $M$.
• 4 X: Se garantiza que $a_X$ consiste en un único elemento. Imprima este único elemento de $a_X$.

Entrada

La primera línea de la entrada contiene un único entero $Q$ ($1 \le Q \le 5 \cdot 10^5$), el número de operaciones.

Las siguientes $Q$ líneas contienen una operación cada una.

Se garantiza que:

• Los índices $X$ e $Y$ utilizados en las operaciones $2$, $3$ y $4$ siempre permanecen dentro de la secuencia en el momento de la operación.
• Los valores $M$ y $K$ utilizados en las operaciones $1$ y $3$ satisfacen $1 \le M,K \le 10^9$.
• Para todas las operaciones de tipo $4$, $a_X$ contiene exactamente un elemento.

Salida

Para cada operación de tipo $4$, imprima una línea con la respuesta.

Subtareas

• ($10$ puntos) $1 \le M \le 10$ para todas las operaciones de tipo $1$ y $3$.
• ($40$ puntos) Se garantiza que en cada operación de tipo $3$, el multiconjunto recién añadido se forma eliminando $K$ copias de $M$ de $a_X$.
• ($50$ puntos) Sin restricciones adicionales.

Ejemplos

Entrada 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

Salida 1

5
6

Nota

Los multiconjuntos son los siguientes:

• $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\}$.