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

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

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

Дворцовый скульптор, чтобы порадовать госпожу, выложил серебром тот самый узор, но увеличенный в два раза: каждой блёклой клетке из воспоминаний детства теперь соответствует квадрат \(2 \times 2\) из серебряных клеток. Для каждой клетки \((x, y)\) из этого набора он выложил серебром клетки \((2x, 2y)\), \((2x, 2y + 1)\), \((2x + 1, 2y)\) и \((2x + 1, 2y + 1)\).

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

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