Вам даны \(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
4000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач