Головоломка#8512
Ви вирішили створити головоломку в рамках кампанії "ребрендинг", яку проводить ваша компанія. У коробці ця головоломка буде виглядати як новий логотип вашої компанії, тобто це буде набір з (дев'яти) з'єднаних одиничних квадратів на прямокутній сітці. Проте ці квадратів не обов'язково будуть з'єднані один з одним, тобто вони можуть утворювати кілька зв'язаних частин (але вам не дозволяється розбивати квадрати посередині). Завдання головоломки полягає в тому, щоб переставити ці частини так, щоб вони утворили квадрат 3 \times 3. При перестановці дозволяється лише зсувати частини, а НЕ повертати чи перевертати їх.
Щоб зробити головоломку складнішою, вам потрібно мати якомога менше частин. За наявним логотипом обчисліть, скільки частин вам потрібно, і як переставити їх у квадрат 3 \times 3.
Слово "зв'язане" в умові задачі означає зв'язність по сусідству.
Перший рядок містить два цілих числа і . Кожен з наступних рядків містить символів, що описують ваш логотип. Символ на логотипі може бути або '.' (крапка), що описує порожній квадрат, або 'X' (велика англійська літера X), що вказує на присутність у квадраті логотипу. Усі символи 'X' утворюють зв'язну фігуру, у вхідних даних є рівно символів 'X'. Перший рядок, останній рядок, перший стовпець і останній стовпець містять принаймні один символ 'X', іншими словами, зайвих порожніх рядків або стовпців логотип не містить.
У першому рядку виведіть найменшу кількість частин , на які можна розрізати логотип. Далі виведіть одне з можливих рішень, а саме в наступних рядках виведіть логотип, у якому всі символи 'X' замінені на перші великі літери англійського алфавіту, кожна літера належить одній частині. Далі виведіть порожній рядок, а потім рядки, кожен з яких містить символи - ці ж частини, зсунуті так, щоб утворити квадрат 3 \times 3.
Усі частини повинні бути зв'язними, значення повинно бути найменшим. Якщо існує кілька рішень, виведіть будь-яке.
Приклад 1