Задана прямоугольная таблица n × m, клетки которой изначально не покрашены. Требуется так разукрасить все клетки таблицы, что полученная раскраска образует замощение таблицы квадратами. Более формально:
- каждая клетка должна быть покрашена в некоторый цвет (цвета обозначаются большими буквами латинского алфавита);
- будем считать, что две клетки таблицы связны, если они одного цвета и имеют общую сторону; каждая связная область раскраски таблицы должна являться квадратом.
По заданным n и m найдите лексикографически минимальную раскраску таблицы, удовлетворяющую описанным свойствам.
Выходные данные
Выведите лексикографически минимальную раскраску таблицы, удовлетворяющую описанным условиям.
Одна раскраска (обозначим ее X) считается лексикографически меньше другой (обозначим ее Y), если:
- будем рассматривать клетки таблицы в порядке слева направо, сверху вниз (сначала самая первая клетка в первой строке, затем вторая клетка в первой строке и так далее);
- найдем первую клетку в таком порядке, цвет которой в двух раскрасках отличается;
- буква, обозначающая цвет этой клетки в X, идет раньше в алфавите, чем буква, обозначающая цвет этой клетки в Y.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 3
|
ABA
|
|
2
|
2 2
|
AA
AA
|
|
3
|
3 4
|
AAAB
AAAC
AAAB
|