Крошечная головоломка
Вы решили создать головоломку в рамках кампании по "ребрендингу", проводимой вашей компанией. В коробке эта головоломка будет выглядеть как новый логотип вашей компании, то есть это будет набор из 9 (девяти) соединенных единичных квадратов на прямоугольной сетке. Однако эти 9 квадратов не обязательно будут все склеены вместе, то есть они могут образовывать несколько соединенных частей (однако вам не разрешается делить квадраты пополам). Цель головоломки будет заключаться в том, чтобы переставить эти части так, чтобы они образовали квадрат 3x3. При перестановке разрешается только сдвигать части, НО не вращать и не переворачивать их.
Чтобы сделать головоломку более сложной, вам нужно иметь как можно меньше частей. Учитывая логотип, вычислите, сколько частей вам нужно и как их переставить в квадрат 3x3.
Каждое слово "соединенные" в условии задачи означает соединенность в смысле бок о бок.
Входные данные
Первая строка входных данных содержит два целых числа H и W. Следующие H строк содержат по W символов, описывающих ваш логотип. Каждый из этих символов будет либо '.' (точка), обозначающая пустой квадрат, либо 'X' (заглавная английская буква X), обозначающая квадрат, занятый логотипом. Все 'X' образуют соединенную фигуру, на входе будет ровно 9 'X'. В первой строке, последней строке, первом столбце и последнем столбце будет как минимум один 'X', другими словами, не будет лишних пустых строк по краям сетки.
Выходные данные
В первой строке выведите требуемое количество частей K. Затем выведите одну из возможных перестановок, а именно: в следующих H строках выведите логотип со всеми 'X', замененными на первые K заглавных букв английского алфавита, каждая буква обозначает одну часть. Затем выведите пустую строку, а затем 3 строки, содержащие по 3 символа каждая, содержащие те же K части, но сдвинутые так, чтобы они образовали квадрат 3x3.
Все части должны быть соединены, и K должно быть минимально возможным. Если существует несколько возможных решений, выведите любое.