Когда она была ещё княжной в небольшом шахматном замке, Амальтея каждый день гуляла по золотому церемониальному залу. Пол церемониального зала представлял собой клетчатую плоскость, разделенную на единичные квадраты. Маршрут Амальтеи был одинаковый каждый день: она вставала на определённую клетку, делала определённые переходы с текущей клетки на соседнюю по стороне и в конце возвращалась на клетку, с которой начала. Поскольку в детстве Амальтее ничего не запрещали, она могла посещать одну и ту же клетку несколько раз.

За много лет таких прогулок золото на клетках, посещаемых Амальтеей, стёрлось и стало выглядеть блёклым. Этот узор Амальтея запомнила на всю жизнь.

Теперь, став графиней в большом шахматном дворце, она решила в память о детстве выложить серебряными плитками в золотом церемониальном зале тот же самый узор.

Дворцовый скульптор, чтобы порадовать госпожу, выложил серебром тот самый узор, но увеличенный в два раза: каждой блёклой клетке из воспоминаний детства теперь соответствует квадрат 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 строк, в каждой из них выведите координаты очередной клетки маршрута Амальтеи во дворце. Каждые две соседние клетки, а также первая и последняя в выведенном маршруте должны быть соседними по стороне. В маршрут должны войти все серебряные клетки.