C. Помогите складовщику
ограничение по времени на тест
3 seconds
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

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

Проблемы у него возникли с самой крупной техникой, которой, разумеется, являются турбоплуги. Проблема в том, что турбоплуг при хранении занимает на складе не обычную прямоугольную форму, а T-образную, как на одной из четырех картинок ниже (где символом «#» обозначено место, занимаемое турбоплугом, символом «.» — свободное пространство):

###      ..#      .#.      #..
.#.      ###      .#.      ###
.#.      ..#      ###      #..

Перед Семеном встала довольно естественная задача: разместить на заданном складе размерами n × m максимальное количество турбоплугов. При хранении турбоплуги можно поворачивать как угодно (так чтобы они занимали область как на одной из четырех картинок выше), однако нельзя, чтобы два турбоплуга «накладывались», то есть занимали общую область склада.

Семен чувствует, что один не сможет найти оптимальное размещение турбоплугов на складе, максимизирующее их общее количество. Поможете ему?

Входные данные

В единственной строке записаны через пробел два целых числа n и m — размеры склада (1 ≤ n, m ≤ 9).

Выходные данные

В первой строке выведите максимальное количество турбоплугов, которое можно разместить на складе. В следующих n строках выведите по m символов. Символом «.» (точка) обозначайте пустое место, последовательными заглавными буквами латинского алфавита («A» — для первого турбоплуга, «B» — для второго, и так далее до количества турбоплугов в вашей схеме) — места для соответствующих турбоплугов при их оптимальном расположении на складе. Порядок нумерации мест для турбоплугов на складе значения не имеет. Если существует несколько оптимальных решений для склада данных размеров — выведите любое.

Примеры
Входные данные
3 3
Выходные данные
1
AAA
.A.
.A.
Входные данные
5 6
Выходные данные
4
A..C..
AAAC..
ABCCCD
.B.DDD
BBB..D
Входные данные
2 2
Выходные данные
0
..
..