Вам даны \(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\) строк. В \(i\)-й из них выведите точку с целочисленными координатами, не принадлежащую заданным \(n\) точкам, и являющуюся ближайшей (по Манхэттенскому расстоянию) к \(i\)-й точке из входных данных.
Выводимые координаты должны находиться в отрезке \([-10^6; 10^6]\). Можно показать, что любой оптимальный ответ удовлетворяет заданным ограничениям.
Если существует несколько возможных ответов, вы можете вывести любой из них.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|
|
2
|
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
|