Стиснення зображення#9053
Агент Джонні Інгліш проник у лігво ворога і виявив там секретне зображення, яке потрібно терміново передати до командного центру. Однак перед передачею його слід стиснути, щоб зменшити час передачі до мінімуму.
Зображення має форму прямокутника розміром на , розділеного на n \times m одиничних клітинок — пікселів. Кожен піксель може бути або чорного, або білого кольору.
Опишемо процес стиснення зображення. Джонні може розділити все зображення на прямокутники однакових розмірів (всі прямокутники повинні мати однакову висоту і ширину). Якщо в результаті цього розбиття в кожному прямокутнику всі пікселі мають однаковий колір, Джонні може замінити кожен такий прямокутник на один піксель відповідного кольору. Для кращого розуміння процесу стиснення зображення ознайомтеся з прикладами тестів.
Допоможіть Джонні знайти спосіб стиснення зображення, який містить мінімальну кількість пікселів.
Перший рядок містить два цілі числа і (1 \le n, m \le 3000) — висота і ширина вихідного зображення відповідно. Далі йдуть рядків, кожен з яких складається з символів, що описують кольори пікселів вихідного зображення. Символ . позначає піксель білого кольору, а символ X — піксель чорного кольору.
Виведіть опис стиснення зображення, дотримуючись того ж формату, що й у вхідних даних.
Приклад 1
Приклад 2
Приклад 3