Eres un ávido investigador de Ethereum. Recientemente, Ethereum aprobó una resolución para cambiar la tarifa de gas de una transacción de un valor Precio a un par (máximaTarifa, máximaPrioridad). El precio exacto del gas de una transacción se calcula mediante Precio=~\min~(máximaTarifa,máximaPrioridad+tarifaBase), mientras que tarifaBase es un parámetro que puede cambiar con el tiempo.

Usted debe mantener una colección dinámica de transacciones. En algunos momentos, se desea saber, para una tarifaBase específica, cuál es el mayor Precio de una transacción en la colección.

Específicamente, debe mantener una colección de transacciones que admita las siguientes operaciones:

• Agregue una transacción con la tarifa de gas (máximaTarifa, máximaPrioridad) a la colección.
• Eliminar una sola transacción con la tarifa de gas (máximaTarifa, máximaPrioridad) de la colección. Se garantiza que existe al menos una transacción que cumple la condición.
• Para una tarifaBase específica, encuentre el valor máximo de Precio en la colección cuando la tarifa base actual es tarifaBase. Se garantiza que hay al menos una transacción en la colección.

Entrada

La primera línea contiene un entero ~t~ (~0 \leq t \leq 10^6~) que representa el número de operaciones. Para las siguientes líneas ~t~, el primer entero ~tipo~ de cada línea representa el tipo de la operación actual.

Si ~tipo=1~, los siguientes dos enteros son máximaTarifa y máximaPrioridad. Debe agregar una transacción con tarifa de gas (máximaTarifa, máximaPrioridad) a la colección.

Si ~tipo=2~, los siguientes dos números enteros son máximaTarifa y máximaPrioridad. Debe eliminar una sola transacción con tarifa de gas (máximaTarifa, máximaPrioridad) de la colección.

Si ~tipo=3~, el siguiente entero es tarifaBase. Debe generar el valor máximo de Precio en la colección cuando la tarifa base actual es tarifaBase.

Se garantiza que todos los valores de máximaTarifa, máximaPrioridad y tarifaBase son números enteros en el rango ~[0,10^6]~.

Salida

Para cada operación con ~tipo=3~, genere una línea con un número entero que represente el mayor Precio cuando la tarifa base actual sea tarifaBase.

Subtareas

• Subtarea 1: Todas las operaciones serán de tipo 1 o 3, es decir, no se eliminará ninguna transacción. máximaPrioridad ~= 10^6~ para todas las transacciones. (10 puntos)
• Subtarea 2: máximaPrioridad ~= 10^6~ para todas las transacciones. (10 puntos)
• Subtarea 3: ~t \le 3000~. Todas las operaciones serán de tipo 1 o 3, es decir, no se eliminará ninguna transacción. (11 puntos)
• Subtarea 4: Todas las operaciones serán de tipo 1 o 3, es decir, no se eliminará ninguna transacción. (35 puntos)
• Subtarea 5: Sin restricciones adicionales. (34 puntos)

Ejemplo de entrada 1

6
1 50 1000000
3 150
1 80 1000000
3 80
1 30 1000000
3 200

Ejemplo de salida 1

50
80
80

Ejemplo de entrada 2

9
1 200000 20000
1 150000 40000
1 120000 50000
1 130000 30000
3 80000
3 100000
3 140000
2 150000 40000
3 100000

Ejemplo de salida 2

120000
140000
160000
130000