Нова прогулянка Амальтеї
Коли Амальтея була ще княжною в невеликому шаховому замку, вона щодня гуляла по золотому церемоніальному залу. Підлога залу була розділена на одиничні квадрати, утворюючи клітчасту площину. Щодня її маршрут був однаковим: вона починала з певного рядка, переходила на сусідні рядки по сторонам і в кінці поверталася на початковий рядок. У дитинстві Амальтеї не було заборон, тому вона могла відвідувати один і той самий рядок кілька разів.
З роками золото на рядках, які відвідувала Амальтея, стерлося, залишивши блідий візерунок, який вона запам'ятала на все життя.
Тепер, ставши графинею у великому шаховому палаці, вона вирішила відтворити цей візерунок у золотому церемоніальному залі, але вже срібними плитками.
Палацовий скульптор виклав сріблом той самий візерунок, але збільшений вдвічі: кожному блідому рядку з дитинства тепер відповідає квадрат 2 * 2 з срібних рядків. Для кожного рядка (x, y) з цього набору він виклав сріблом рядки (2x, 2y), (2x, 2y + 1), (2x + 1, 2y) і (2x + 1, 2y + 1).
Скульптора вже стратили, але тепер Амальтея хоче навчитися обходити новий срібний набір рядків. Вона знову буде ходити з рядка тільки на сусідній по стороні, і знову повинна в кінці повернутися на рядок, з якого почала. Але тепер, через суворі правила палацового етикету, вона не має права відвідувати один і той самий рядок двічі, за винятком останнього кроку на початковий рядок.
Щоб уникнути страти палацового математика, побудуйте коректний маршрут для Амальтеї.
Вхідні дані
У першому рядку задано ціле число n (1 ≤ n ≤ 30 000) - кількість блідих рядків у візерунку з дитинства.
Кожен з наступних n рядків містить два цілі числа x[i], y[i] (0 ≤ x[i], y[i] ≤ 1000) - координати блідого рядка.
Гарантовано, що жоден рядок не повторюється, і що область з цих рядків є зв'язною по стороні.
Вихідні дані
Виведіть 4n рядків, у кожному з них виведіть координати чергового рядка маршруту Амальтеї у палаці. Кожні два сусідні рядки, а також перший і останній у виведеному маршруті повинні бути сусідніми по стороні. У маршрут повинні увійти всі срібні рядки.