Бизнесмены средней важности хотят организовать встречу в Бахэттане. Карта Бахэттана напоминает бесконечную двумерную сетку, где авеню соответствуют вертикальным прямым вида $x = a$ для целых $a$, а улицы — горизонтальным прямым вида $y = b$ для целых $b$. Каждая такая авеню и улица пересекаются в точке с координатами $(a, b)$. Из точки с координатами $(a, b)$ можно переместиться в точку с координатами $(a \pm 1, b)$ или $(a, b \pm 1)$ ровно за одну минуту.
Всего есть $n$ бизнесменов, пронумерованных от $1$ до $n$. Перед встречей $i$-й бизнесмен (для $1 \le i \le n$) находится в отеле, расположенном в точке с координатами $(x_i, y_i)$.
Бизнесмены хотят встретиться в какой-нибудь точке пересечения как можно скорее. Как только они выбирают место встречи, каждый из них одновременно начинает путь к нему из своего отеля, выбирая кратчайший возможный маршрут. Как известно, неудобно ждать последнего человека, или даже последних двух или трех. Поэтому вас попросили определить для каждого целого числа $k$ в диапазоне от $1$ до $n$ такую точку пересечения $(x, y)$, что если встреча будет организована в этой точке, то ровно $k$ бизнесменов прибудут на встречу последними, либо сообщить, что такой точки не существует. Другими словами, мы хотим, чтобы ровно $k$ бизнесменов оказались на встрече в тот же самый момент, что и самые последние прибывшие.
Входные данные
Первая строка входных данных содержит единственное целое число $n$ ($1 \le n \le 10^6$), обозначающее количество бизнесменов. Следующие $n$ строк описывают расположение их отелей. $i$-я строка (для $1 \le i \le n$) содержит два целых числа $x_i, y_i$ ($-10^9 \le x_i, y_i \le 10^9$), описывающих координаты отеля, в котором остановился $i$-й бизнесмен. Может случиться так, что в одном и том же отеле остановилось более одного бизнесмена.
Выходные данные
Вы должны вывести $n$ строк. $k$-я строка (для $1 \le k \le n$) должна содержать два целых числа $a_k, b_k$ ($-10^{18} \le a_k, b_k \le 10^{18}$), означающих, что если встреча организована в точке $(a_k, b_k)$, то ровно $k$ бизнесменов прибудут туда последними, либо единственное слово NIE, если такой точки не существует. Если существует несколько таких точек, вы можете вывести любую из них.
Примеры
Входные данные 1
5 -1 0 3 0 -2 -1 1 2 1 -1
Выходные данные 1
1 0 0 -1 0 0 1 -1 NIE
Входные данные 2
3 0 3 0 3 1 1
Выходные данные 2
0 2 1 1 NIE
Примечание
Пояснение к первому примеру: на рисунке ниже показаны примеры путей для наиболее задержавшихся бизнесменов при $i = 3$.
Пояснение к первому примеру: на рисунке ниже показаны примеры путей для наиболее задержавшихся бизнесменов для i = 3.
Подзадачи
Набор тестов разделен на следующие подзадачи. Тесты для каждой подзадачи состоят из одной или нескольких отдельных групп тестов.
| Подзадача | Ограничения | Баллы |
|---|---|---|
| 1 | $n, \left\lvert x_i\right \rvert, \left\lvert y_i\right \rvert \le 50$ | 13 |
| 2 | $\left\lvert x_i\right \rvert, \left\lvert y_i\right \rvert \le 50$ | 16 |
| 3 | $n \le 3$ и все $x_i, y_i$ четные | 19 |
| 4 | для каждого отеля $x_i \ge 0$ и $\left\lvert y_i\right\rvert = x_i$ | 23 |
| 5 | без дополнительных ограничений | 29 |
Оценивание
Решение будет проверяться на следующих группах тестов:
- 0a: примеры из условия
- 0b: тесты для подзадачи 1
- 0c: $n = 42$, $i$-й бизнесмен ночует в отеле с координатами $x_i = i, y_i = i + (i \pmod 3)$
- 0d: $n = 102\,010$, при каждом пересечении $(x, y)$ таком, что $|x|, |y| \le 50$, ночует ровно десять бизнесменов
- 0e: $n = 3$, отели находятся в точках $(10^9, 10^9), (-10^9, 10^9), (-10^9, -10^9)$
- 0f: $n = 4 \cdot 10^4$, $i$-й бизнесмен ночует в отеле с координатами $x_i = i \cdot 10^4, y_i = i \cdot (-1)^i \cdot 10^4$
- 0g: $n = 10^6$, каждый отель лежит на одной из четырех прямых вида $y = \pm x \pm 10^9$