D. Ближайшие точки
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны $$$n$$$ различных точек на плоскости. Координаты $$$i$$$-й из них — $$$(x_i, y_i)$$$.

Для каждой точки $$$i$$$ вам необходимо найти ближайшую (по Манхэттенскому расстоянию) точку с целочисленными координатами, которая не принадлежит множеству заданных $$$n$$$ точек. Если существует несколько таких точек, вы можете выбрать любую из них.

Манхэттенское расстояние между двумя точками $$$(x_1, y_1)$$$ и $$$(x_2, y_2)$$$ равно $$$|x_1 - x_2| + |y_1 - y_2|$$$.

Входные данные

Первая строка входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество точек в множестве.

Следующие $$$n$$$ строк описывают точки. В $$$i$$$-й из них находится два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$1 \le x_i, y_i \le 2 \cdot 10^5$$$) — координаты $$$i$$$-й точки.

Гарантируется, что все точки во входных данных различны.

Выходные данные

Выведите $$$n$$$ строк. В $$$i$$$-й из них выведите точку с целочисленными координатами, не принадлежащую заданным $$$n$$$ точкам, и являющуюся ближайшей (по Манхэттенскому расстоянию) к $$$i$$$-й точке из входных данных.

Выводимые координаты должны находиться в отрезке $$$[-10^6; 10^6]$$$. Можно показать, что любой оптимальный ответ удовлетворяет заданным ограничениям.

Если существует несколько возможных ответов, вы можете вывести любой из них.

Примеры
Входные данные
6
2 2
1 2
2 1
3 2
2 3
5 5
Выходные данные
1 1
1 1
2 0
3 1
2 4
5 4
Входные данные
8
4 4
2 4
2 2
2 3
1 4
4 2
1 3
3 3
Выходные данные
4 3
2 5
2 1
2 5
1 5
4 1
1 2
3 2