Dados dos conjuntos múltiples ~U~ y ~V~ que contienen puntos en dos dimensiones con coordenadas enteras.

Definamos la función ~D(U, V)~ para un par de conjuntos múltiples como:

• ~D(U, V) = -1~ si alguno de los conjuntos múltiples está vacío.
• ~D(U, V) = \min\limits_{\begin{smallmatrix}(u_x, u_y) \in U \\ (v_x, v_y) \in V\end{smallmatrix}}\max(u_x + v_x, u_y + v_y)~ si ambos conjuntos múltiples contienen al menos un elemento.

Al principio, ambos ~U~ y ~V~ están vacíos. Procese ~Q~ consultas de la sigiente forma:

• ~1~ ~s~ ~x~ ~y~: Añade el punto ~(x, y)~ a uno de los conjuntos múltiples. Si ~s = 1~, añade el punto a ~U~. De lo contrario, añade el punto a ~V~.
• ~2~ ~s~ ~x~ ~y~: Elimina el punto ~(x, y)~ de uno de los conjuntos múltiples. Si ~s = 1~, elimina el punto de ~U~. De lo contrario, elimina el punto de ~V~.

Después de eliminar un punto, si hay varios puntos en las coordenadas dadas, usted debe eliminar solo uno de ellos. Se garantiza que el punto dado existe en el conjunto múltiple dado en el momento de cada eliminación.

Su tarea es procesar todas las consultas. Luego de cada consulta, Imprime ~D(U, V)~.

Entrada

La primera línea contiene un solo entero ~Q~ (~1 \le Q \le 250\,000~).

Cada una de las siguientes ~Q~ líneas contiene una consulta de la forma descrita arriba.

Para todas las consultas se cumple que: ~s \in \{1, 2\}~, ~0 \le x, y \le 250\,000~.

Salida

Imprime ~Q~ líneas. Cada línea debe contener el valor ~D(U, V)~ después de la consulta correspondiente.

Subtareas

• Subtarea 1: Todas las operaciones son de tipo ~1~, es decir, solo se insertarán elementos, ~Q \le 100~. (8 puntos)
• Subtarea 2: ~Q \le 100~. (9 puntos)
• Subtarea 3: Todas las operaciones son de tipo ~1~, es decir, solo se insertarán elementos, ~Q \le 4\,000~. (6 puntos)
• Subtarea 4: ~Q \le 4\,000~. (11 puntos)
• Subtarea 5: Todas las operaciones son de tipo ~1~, es decir, solo se insertarán elementos. (25 puntos)
• Subtarea 6: ~Q \le 50\,000~. (37 puntos)
• Subtarea 7: Sin restricciones adicionales (4 puntos)

Ejemplo de entrada 1

4
1 1 2 1
1 1 2 1
1 2 2 1
1 2 1 2

Ejemplo de salida 1

-1
-1
4
3

Ejemplo de entrada 2

6
1 1 100 100
1 2 30 130
1 1 120 170
2 1 100 100
1 2 70 100
2 1 120 170

Ejemplo de salida 2

-1
230
230
300
270
-1