ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1298. Конь

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

Исходные данные

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

Результат

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

Примеры

исходные данныерезультат
3
IMPOSSIBLE
5
a1
c2
e1
d3
e5
c4
d2
e4
c5
a4
b2
d1
e3
d5
b4
a2
c1
e2
c3
b1
a3
b5
d4
b3
a5
Автор задачи: Фольклор. Подготовил: Ден Расковалов
Источник задачи: IX Открытое командное соревнование школьников по программированию (13.03.2004)