Головоломка
Вы решили сделать головоломку в рамках кампании "ребрендинг", проводимой вашей компанией. В коробке эта головоломка будет выглядеть как новый логотип вашей компании, то есть это будет набор из 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 должно быть наименьшим. Если существует несколько решений, выведите любое.