Des hommes d'affaires d'importance moyenne souhaitent organiser une réunion à Bajhattan. La carte de Bajhattan ressemble à une grille bidimensionnelle infinie, où les avenues correspondent aux lignes verticales de la forme $x = a$ pour des entiers $a$, et les rues correspondent aux lignes horizontales de la forme $y = b$ pour des entiers $b$. Chaque avenue et chaque rue se croisent pour former une intersection aux coordonnées $(a, b)$. Depuis une intersection aux coordonnées $(a, b)$, on peut se déplacer vers une intersection aux coordonnées $(a \pm 1, b)$ ou $(a, b \pm 1)$ en exactement une minute.

Il y a $n$ hommes d'affaires, numérotés de $1$ à $n$. Avant la réunion, le $i$-ème homme d'affaires (pour $1 \le i \le n$) séjourne dans un hôtel situé à l'intersection aux coordonnées $(x_i, y_i)$.

Les hommes d'affaires veulent se réunir à une intersection donnée le plus tôt possible. Dès qu'ils décident du lieu de réunion, tout le monde commence simultanément son trajet depuis son hôtel, en choisissant le chemin le plus court possible. Comme chacun le sait, il est gênant d'attendre la dernière personne, ou même les deux ou trois dernières. C'est pourquoi il vous est demandé de déterminer, pour chaque entier $k$ compris entre $1$ et $n$, une intersection $(x, y)$ telle que si la réunion est organisée à cette intersection, exactement $k$ hommes d'affaires arrivent en dernier, ou d'indiquer qu'une telle intersection n'existe pas. En d'autres termes, nous voulons qu'exactement $k$ hommes d'affaires arrivent à la réunion au même moment que les derniers.

Entrée

La première ligne de l'entrée contient un entier unique $n$ ($1 \le n \le 10^6$) désignant le nombre d'hommes d'affaires. Les $n$ lignes suivantes décrivent l'emplacement de leurs hôtels. La $i$-ème ligne (pour $1 \le i \le n$) contient deux entiers $x_i, y_i$ ($-10^9 \le x_i, y_i \le 10^9$) décrivant les coordonnées de l'hôtel où séjourne le $i$-ème homme d'affaires. Il est possible que plusieurs hommes d'affaires séjournent dans le même hôtel.

Sortie

Vous devez afficher $n$ lignes. La $k$-ème ligne (pour $1 \le k \le n$) doit contenir deux entiers $a_k, b_k$ ($-10^{18} \le a_k, b_k \le 10^{18}$) indiquant que si la réunion est organisée à l'intersection $(a_k, b_k)$, exactement $k$ hommes d'affaires arriveront en dernier, ou le mot unique NIE si aucune telle intersection n'existe. S'il existe plusieurs intersections de ce type, vous pouvez en afficher n'importe laquelle.

Exemples

Entrée 1

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

Sortie 1

1 0
0 -1
0 0
1 -1
NIE

Entrée 2

3
0 3
0 3
1 1

Sortie 2

0 2
1 1
NIE

Remarque

Explication pour le premier exemple : Le dessin ci-dessous montre des exemples de chemins pour les hommes d'affaires les plus retardés pour $i = 3$.

Poniższy rysunek przedstawia przykładowe ścieżki najbardziej spóźnionych biznesmenów dla i = 3.