La capital ideal Eldiana, puede ser representada como una grilla donde solo es posible desplazarse paralelamente a los ejes ~X~ e ~Y~. La compañía "Sasha's Pizzas" 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~.

Entrada:

La entrada contendrá las siguientes lineas: Línea ~1~: Un entero ~T~, la cantidad de “ordenes”. Línea ~2..T+1~: cada una con una orden de acuerdo al formato especificado anteriormente.

Salida:

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

Restricciones:

• ~2 \le T \le 100000~.
• ~0 \le x, y \le 100000~.

Para ~\frac{3}{14}~ de los casos se garantiza que ~2 \le T \le 2000~.

Ejemplo de entrada:

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

Ejemplo de salida:

6
3
3