Su tarea consiste en procesar eficientemente los siguientes tipos de consultas:

1. Añadir una línea ~ax+b~
2. Encontrar el punto máximo en cualquier línea en la posición ~x~

Entrada

La primera línea tiene un entero ~n~: el número de consultas. Las siguientes ~n~ líneas describen las consultas. El formato de cada línea es "~1~ ~a~ ~b~" o "~2~ ~x~". Puede asumir que la primera consulta es de tipo ~1~.

Salida

Imprimir la respuesta para cada consulta de tipo ~2~.

Restricciones

• ~1 \leq n \leq 2 \cdot 10^5~
• ~-10^9 \leq a,b \leq 10^9~
• ~0 \leq x \leq 10^5~

Ejemplo de Entrada

6
1 1 2
2 1
2 3
1 0 4
2 1
2 3

Ejemplo de Salida

3
5
4
5