La capital ideal de la CIIC, puede ser representada como una grilla donde solo es posible desplazarse paralelamente a los ejes ~X~ e ~Y~. La compañía CIICPizza quiere un programa para mantener un registro de todas sus pizzerías y además que pueda determinar el tiempo mínimo de entrega para un determinado punto (o sea la pizzería más cercana).

La compañía necesita que su programa sea capaz de procesar órdenes de la siguiente forma:

I x y: agregar una pizzería en las coordenadas enteras ~(x,y)~. Inicialmente no hay pizzerías disponibles.

D x : imprimir el tiempo de entrega mínimo (de las pizzerías disponibles) a las coordenadas enteras ~(x, 0)~, o sea sobre el eje ~x~.

Usted tiene como tarea hacer un programa que permita:

• Leer desde la entrada la cantidad y las órdenes a procesar.
• Determinar el tiempo de entrega mínimo para cada orden ~D~.
• Escribir hacia la salida todos los tiempos mínimos para cada orden ~D~.

Entrada

Línea 1: Un entero ~O~, la cantidad de “órdenes”. Línea 2..O+1: cada una con una orden de acuerdo al formato especificado anteriormente.

Salida

La salida contiene para cada orden ~D x~, el tiempo de entrega mínimo. Se garantiza que siempre habrá al menos 1 pizzería disponible.

Restricciones

• ~2 \leq O \leq 100000~.
• ~0 \leq x, y \leq 100000~.

Ejemplo de Entrada

5
I 4 3
D 1
I 2 2
D 1
D 4

Ejemplo de Salida

6
3
3