eolymp
bolt
Try our new interface for solving problems
Problems

Раздел королевства

Раздел королевства

Time limit 2 seconds
Memory limit 512 MiB

Правивший много лет король Байтландии Байтазар Большое Гнездо задумал приучить своих наследников к государственным делам. Для этого он собирается разделить своё королевство на герцогства и распределить между своими сыновьями. Проблема заключается в том, что детей у Байтазара много... реально много.

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

Королевство можно представить как прямоугольник n×m, разбитый на n·m единичных квадратов. Каждое герцогство должно быть составлено из целого числа единичных квадратов и должно быть связным по стороне (то есть между каждыми двумя единичными квадратами, входящими в герцогство, существует путь, полностью составленный из входящих в герцогство единичных квадратов, в котором каждый следующий квадрат имеет с предыдущим общую сторону). Каждый квадрат должен принадлежать ровно одному герцогству.

Король планирует разделить королевство так, чтобы как можно большее количество наследников получило свои герцогства. Помогите ему сделать это.

Input data

Единственная строка входа содержит два целых числа n и m (1n, m1000), обозначающие размеры прямоугольника.

Output data

В первой строке выведите одно целое число k: наибольшее количество наследников, которые могут получить своё герцогство. Каждая из последующих n строк должна содержать по m символов - заглавных латинских букв из множества {A, ..., Z} - отображения герцогств. Отдельному герцогству соответствует связная часть, составленная из одинаковых букв и граничащая по сторонам только с частями, обозначенными другими буквами. Отметим, что различные части при этом вполне могут быть обозначены одной и той же буквой. При этом для любых двух частей количество составляющих эти части букв должно быть различно.

Гарантируется, что для любого соответствующего условиям задачи разбиения существует способ обозначить вышеописанным образом его части, использовав не более чем 26 букв.

Examples

Input example #1
4 5
Output example #1
5
ABBCC
DDDDC
EEEEE
EEEEE
Source Yandex.Algorithm, Online Round 1, July 14, 2013