Альянси#5341
У фантастичному світі існує великий острів прямокутної форми. Його сторони мають довжину миль і миль, і весь острів поділений на сітку з R \times C ділянок. Деякі з цих ділянок є незаселеними, а інші зайняті селами фантастичних істот: ельфів, людей, гномів та гобітів. Кожна ділянка може містити не більше одного села. Два села вважаються сусідами, якщо їх ділянки мають спільну сторону.
Нещодавно села стали боятися Великого Зла. Щоб почуватися безпечніше, кожне село вирішило утворити військові союзи з деякими зі своїх сусідів. Союз завжди включає два сусідні села, і це взаємна та симетрична угода.
Залежно від виду, що живе в селі, жителі не відчуватимуть себе в безпеці, якщо не буде утворена певна конфігурація союзів:
Ельфи відчувають себе впевнено, і тому потребують рівно одного союзу.
Людські села потребують союзів з рівно двома сусідами. Більше того, залишати дві протилежні сторони села відкритими погано з тактичних причин. Тому двоє союзних сусідів не можуть бути розташовані на протилежних сторонах села.
Гноми потребують союзів з рівно трьома сусідами.
Гобіти дуже налякані, і тому потребують союзів з усіма чотирма своїми сусідами.
Іншими словами, крім людей, кожне село потребує певної кількості союзів, але не має значення, які сусіди будуть його союзниками. Для людей є додаткове обмеження: союзні сусіди не повинні бути на протилежних сторонах села.
Умови повинні бути виконані незалежно від розташування села на карті. Наприклад, село гномів бажає трьох союзів. Якщо воно розташоване на узбережжі, це означає, що воно повинно мати союзи з усіма трьома сусідами. Якщо село гномів знаходиться в кутку острова, його жителі ніколи не почуватимуться в безпеці.
Для заданого опису острова ваше завдання - вирішити, чи можливо утворити союзи так, щоб усі жителі острова почувалися в безпеці. У разі позитивної відповіді, ваше завдання також запропонувати одну можливу конфігурацію союзів. У разі кількох рішень виберіть будь-яке з них.
Перший рядок вхідних даних містить два цілі числа і , що вказують розмір острова. Наступні рядків кодують опис острова. Кожен рядок складається з чисел, розділених пробілами, від до :
означає незаселену ділянку,
означає село ельфів,
означає людське село,
означає село гномів,
означає село гобітів.
(Зверніть увагу, що число у вхідних даних завжди відповідає кількості бажаних союзів для цього села.)
Обмеження
У всіх тестових випадках припускається, що 1 \leq R, C \leq 70.
У тестових випадках, що варті загалом балів, маємо \min(R, C) \leq 10. З них у тестових випадках, що варті балів, R \cdot C \leq 20.
Інша партія тестових випадків, що варті балів, містить карти лише з незаселеними ділянками та людськими селами. (Ця партія не включена в тестові випадки, що варті балів.)
Якщо рішення немає, виведіть один рядок із текстом "Impossible!" (лапки для ясності). Інакше виведіть одну дійсну карту союзів у наступному форматі.
Кожна ділянка повинна з'явитися у вихідних даних як матриця з 3 \times 3 символів. Якщо ділянка незаселена, відповідна частина виходу буде заповнена символами . (крапка). Якщо на ділянці є село, має бути символ O (велика літера O) посередині, що представляє саме село, і повинні бути символи X (велика літера X), що представляють конфігурацію його союзників. Решта матриці повинна бути заповнена символами . (крапка).
Для кожного типу села всі можливі розташування союзів показані на зображенні нижче.
Приклад 1