Головоломка
Ви вирішили створити головоломку в рамках кампанії "ребрендинг", яку проводить ваша компанія. У коробці ця головоломка буде виглядати як новий логотип вашої компанії, тобто це буде набір з 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 повинно бути найменшим. Якщо існує кілька рішень, виведіть будь-яке.