Новая прогулка Амальтеи
Новая прогулка Амальтеи
Когда она была ещё княжной в небольшом шахматном замке, Амальтея каждый день гуляла по золотому церемониальному залу. Пол церемониального зала представлял собой клетчатую плоскость, разделенную на единичные квадраты. Маршрут Амальтеи был одинаковый каждый день: она вставала на определённую клетку, делала определённые переходы с текущей клетки на соседнюю по стороне и в конце возвращалась на клетку, с которой начала. Поскольку в детстве Амальтее ничего не запрещали, она могла посещать одну и ту же клетку несколько раз.
За много лет таких прогулок золото на клетках, посещаемых Амальтеей, стёрлось и стало выглядеть блёклым. Этот узор Амальтея запомнила на всю жизнь.
Теперь, став графиней в большом шахматном дворце, она решила в память о детстве выложить серебряными плитками в золотом церемониальном зале тот же самый узор.
Дворцовый скульптор, чтобы порадовать госпожу, выложил серебром тот самый узор, но увеличенный в два раза: каждой блёклой клетке из воспоминаний детства теперь соответствует квадрат 2 * 2 из серебряных клеток. Для каждой клетки (x, y) из этого набора он выложил серебром клетки (2x, 2y), (2x, 2y + 1), (2x + 1, 2y) и (2x + 1, 2y + 1).
Скульптора уже казнили, но теперь Амальтея хочет научиться обходить новый серебряный набор клеток. Она снова будет ходить из клетки только на соседнюю по стороне, снова должна в конце вернуться на клетку, из которой начала, но теперь, поскольку дворцовый этикет требует соблюдения строгих правил, она не имеет права посещать одну и ту же клетку дважды, за исключением последнего шага на начальную клетку.
Чтобы избежать казни дворцового математика, постройте корректный маршрут для Амальтеи.
Входные данные
В первой строке задано целое число n (1 ≤ n ≤ 30 000) - количество блёклых клеток в узоре из детства.
Каждая из последующих n строк содержит два целых числа xi
, yi
(0 ≤ xi
, yi
≤ 1000) - координаты блёклой клетки.
Гарантируется, что никакая клетка не повторяется, и что область из этих клеток является связной по стороне.
Выходные данные
Выведите 4n строк, в каждой из них выведите координаты очередной клетки маршрута Амальтеи во дворце. Каждые две соседние клетки, а также первая и последняя в выведенном маршруте должны быть соседними по стороне. В маршрут должны войти все серебряные клетки.
3 0 0 0 1 1 0
0 0 0 1 0 2 0 3 1 3 1 2 1 1 2 1 3 1 3 0 2 0 1 0