Задача D. Обход доски конем

Автор:Общеизвестная   Ограничение времени:10 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

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

Формат входного файла

Первая строка входного файла содержит целые положительные числа N и M — ширина и высота участка шахматной доски соответственно.

Формат выходного файла

Выведите в выходной файл текстовую строку — последовательность клеток в том порядке в котором их должен пройти конь. Каждая клетка должна присутствовать в ответе ровно один раз. Каждый элемент, задающий позицию должен состоять из буквы латинского алфавита и цифры. Соседние элементы разделяются пробелами. Если решения не существует, выведите "No solution".

Ограничения

1 ≤ N * M ≤ 30

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
1 1
A1
2
1 2
No solution
3
3 4
A1 B3 C1 A2 B4 C2 A3 B1 C3 A4 B2 C4

0.036s 0.009s 15