Un grupo de empresarios de mediana importancia desea organizar una reunión en Bajhattan. El mapa de Bajhattan se asemeja a una cuadrícula bidimensional infinita, donde las avenidas corresponden a líneas verticales de la forma $x = a$ para enteros $a$, y las calles corresponden a líneas horizontales de la forma $y = b$ para enteros $b$. Cada avenida y calle se cruzan para formar una intersección con coordenadas $(a, b)$. Desde una intersección con coordenadas $(a, b)$, uno puede moverse a una intersección con coordenadas $(a \pm 1, b)$ o $(a, b \pm 1)$ en exactamente un minuto.

Hay $n$ empresarios, numerados del $1$ al $n$. Antes de la reunión, el $i$-ésimo empresario (para $1 \le i \le n$) se hospeda en un hotel ubicado en la intersección con coordenadas $(x_i, y_i)$.

Los empresarios quieren reunirse en alguna intersección lo antes posible. Tan pronto como deciden el lugar de reunión, todos comienzan simultáneamente su viaje hacia él desde sus hoteles, eligiendo el camino más corto posible. Como es bien sabido, es incómodo esperar a la última persona, o incluso a las últimas dos o tres. Es por eso que se le ha pedido determinar, para cada entero $k$ en el rango de $1$ a $n$, una intersección $(x, y)$ tal que si la reunión se organiza en esta intersección, exactamente $k$ empresarios lleguen a la reunión en último lugar, o indicar que no existe tal intersección. En otras palabras, queremos que exactamente $k$ empresarios aparezcan en la reunión en el mismo momento que los últimos.

Entrada

La primera línea de la entrada contiene un único entero $n$ ($1 \le n \le 10^6$) que denota el número de empresarios. Las siguientes $n$ líneas describen las ubicaciones de sus hoteles. La $i$-ésima línea (para $1 \le i \le n$) contiene dos enteros $x_i, y_i$ ($-10^9 \le x_i, y_i \le 10^9$) que describen las coordenadas del hotel donde se hospeda el $i$-ésimo empresario. Puede ocurrir que más de un empresario se hospeda en el mismo hotel.

Salida

Debe imprimir $n$ líneas. La $k$-ésima línea (para $1 \le k \le n$) debe contener dos enteros $a_k, b_k$ ($-10^{18} \le a_k, b_k \le 10^{18}$) indicando que si la reunión se organiza en la intersección $(a_k, b_k)$, exactamente $k$ empresarios llegarán allí en último lugar, o la palabra NIE si no existe tal intersección. Si existen múltiples intersecciones de este tipo, puede imprimir cualquiera de ellas.

Ejemplos

Entrada 1

5
-1 0
3 0
-2 -1
1 2
1 -1

Salida 1

1 0
0 -1
0 0
1 -1
NIE

Entrada 2

3
0 3
0 3
1 1

Salida 2

0 2
1 1
NIE

Nota

Explicación para el primer ejemplo: El dibujo a continuación muestra rutas de ejemplo para los empresarios con mayor retraso para $i = 3$.

Testy przykładowe

Los casos 0a y 0b son los ejemplos anteriores. Además:

0c: $n = 42$, el $i$-ésimo empresario se hospeda en el hotel con coordenadas $x_i = i, y_i = i + (i \pmod 3)$.

0d: $n = 10 \cdot 10^{12} = 10^{13} + 10$, en cada intersección $(x, y)$ tal que $|x|, |y| \le 50$ se hospedan exactamente diez empresarios.

0e: $n = 3$, los hoteles se encuentran sucesivamente en los puntos $(10^9, 10^9), (-10^9, 10^9), (-10^9, -10^9)$.

0f: $n = 4 \cdot 10^4$, el $i$-ésimo empresario se hospeda en el hotel con coordenadas $x_i = i \cdot 10^4, y_i = i \cdot (-1)^i \cdot 10^4$.

0g: $n = 10^6$, cada hotel se encuentra en una de las cuatro líneas con la ecuación $y = \pm x \pm 10^9$.

Ocenianie

El conjunto de pruebas se divide en las siguientes subtareas. Las pruebas para cada subtarea consisten en uno o más grupos de pruebas separados.