И у десантников бывают выходные. Перелет до Сириуса в недрах “Адмирала Бриско” Лео Хао коротал за шахматной доской. Нет, ему не доставляла удовольствия обычная шахматная игра, да и соперника подходящего не было. Весь день развлекался Лео тем, что пытался обойти все клетки шахматной доски конём так, чтобы конь побывал на каждой клетке всего один раз. Попытался один раз, второй, но постоянно что-то не получалось. Лео начал немного злиться. Раз не получается с доской 8×8, Лео решил попробовать на доске 4×4. И вновь неудача за неудачей. Немного злой, с шахматной доской, зажатой под мышкой, Лео отправился искать местного программиста. Уж вдвоём-то они точно справятся с этой задачкой.

В единственной строке дано целое число N (1 ≤ N ≤ 8).

Если обход квадратного поля N на N клеток конём возможен, выведите N² строк, содержащих правильный обход шахматного поля, иначе единственное слово “IMPOSSIBLE”.

Если вы решили эту задачу, обратите также внимание на задачу "Кошмарный конь".