eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Головоломка

Головоломка

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Вы решили сделать головоломку в рамках кампании "ребрендинг", проводимой вашей компанией. В коробке эта головоломка будет выглядеть как новый логотип вашей компании, то есть это будет набор из 9 (девяти) соединенных единичных квадратов на прямоугольной сетке. Однако эти 9 квадратов не обязательно будут склеены друг с другом, то есть они могут образовывать несколько связанных частей (однако Вам не разрешается разбивать квадраты посередине). Задача головоломки будет состоять в том, чтобы переставить эти части так, чтобы они составляли квадрат 3 * 3. При перестановке разрешается только сдвигать части, а НЕ поворачивать или переворачивать их.

Чтобы сделать головоломку более сложной, Вам необходимо иметь как можно меньше частей. По имеющемуся логотипу вычислите, сколько частей Вам нужно, и как переставить их в квадрат 3 * 3.

Слово "связанное" в условии задачи означает связность в бок о бок.

Вхідні дані

Первая строка содержит два целых числа h и w. Каждая из следующих h строк содержит w символов, описывающих Ваш логотип. Символ на логотипе может быть либо '.' (точка), описывающий пустой квадрат, или X (заглавная английская буква X), указывающий на присутствие в квадрате логотипа. Все символы X образуют связную фигуру, во входных данных имеется в точности 9 символов X. Первая строка, последняя строка, первый столбец и последний столбец содержат как минимум один символ X, другими словами лишних пустых строк или столбцов логотип не содержит.

Вихідні дані

В первой строке выведите наименьшее количество частей k, на которое можно разрезать логотип. Далее выведите одно их возможных решений, а именно в следующих h строках выведите логотип в котором все символы X заменены на первые k заглавных букв английского алфавита, каждая буква принадлежит одной части. Далее выведите пустую строку, а затем 3 строки, каждая из которых содержит 3 символа - эти же k частей, сдвинутые так чтобы образовать квадрат 3 * 3.

Все части должны быть связными, значение k должно быть наименьшим. Если существует несколько решений, выведите любое.

Приклад

Вхідні дані #1
4 5
....X
....X
..XXX
XXXX.
Вихідні дані #1
3
....A
....C
..CCC
BBCC.

BBC
CCC
CCA
Джерело 2007 Петрозаводск, Petr Mitrichev Contest 2, Январь 30, Задача I