Нова прогулянка Амальтеї#8718
Коли вона була принцесою в маленькому шаховому замку, Амальтея щодня гуляла у золотій церемоніальній залі. Підлога зали була поділена на клітини розміром 1 \times 1. Маршрут Амальтеї щодня був однаковий: вона починала з певної клітини, здійснювала певні переміщення до сусідньої по стороні клітини та поверталася до початкової клітини. Оскільки в дитинстві не було жодних заборон, одну й ту ж клітину можна було відвідати кілька разів.
Після багатьох років таких прогулянок золото на відвіданих клітинах потьмяніло. Вона запам'ятала цей малюнок на все життя.
Тепер, ставши графинею у великому шаховому палаці, вона вирішила відновити цей візерунок за допомогою срібних плиток у новій золотій церемоніальній залі, щоб згадувати своє дитинство.
Королівський скульптор виклав цей візерунок срібними плитками, але щоб догодити володарці, зробив візерунок удвічі більшим. Тепер кожна потьмяніла клітина з дитинства відповідає квадрату 2 \times 2 зі срібних плиток. Для кожної клітини (, ) скульптор розмістив срібні плитки у клітинах (, ), (, 2y + 1), (2x + 1, ) та (2x + 1, 2y + 1).
Тепер Амальтея хоче дізнатися, як проходити новим набором срібних клітин. Як і раніше, вона може пересуватися лише у сусідню по стороні клітину. Як і раніше, вона має завершити маршрут, повернувшись у початкову клітину. Але тепер, оскільки етикет у палаці досить суворий, не можна відвідувати одну й ту саму клітину двічі або більше. Виняток — це повернення у початкову клітину в останньому ході.
Допоможіть Амальтеї знайти коректний маршрут для цього нового візерунка.
Перший рядок містить одне ціле число (1 \leq n \leq 30000) — кількість клітин у візерунку з дитинства.
Кожен із наступних рядків містить по два цілих числа x_i, y_i (0 \leq x_i, y_i \leq 1000) — координати потьмянілої клітини.
Гарантується, що жодна клітина не задана двічі, а область є зв'язною по стороні.
Виведіть рядків, у кожному з яких — координати відповідної клітини маршруту Амальтеї у палаці. Кожні дві послідовні клітини, а також перша і остання клітини повинні мати спільну сторону. Маршрут має пройти через усі клітини, викладені сріблом.
Приклад 1