Пікселі#9706

Пікселі

1 секунда

128 мегабайтів

Складна

Існує багато способів захисту дикої природи. Один із них — створення плакатів, які можуть надихати людей, і саме цим займаються художники. Серед тих, хто потребує натхнення, є вундеркінди, тому деякі художники обирають піксельне мистецтво.

Художник підготував чорно-біле піксельне зображення тварин. Це зображення необхідно відобразити на гігантському прямокутному екрані з $k$ рядками (пронумерованими від $0$ до $k - 1$ k - 1 зверху вниз) та $l$ стовпцями (пронумерованими від $0$ до $l - 1$ l - 1 зліва направо).

Спочатку екран повністю білий. Кожен піксель можна перемикати незалежно за допомогою кнопки: натискання кнопки пікселя $p$ змінює його колір (з білого на чорний або навпаки). Однак екран несправний: натискання кнопки пікселя $p$ також перемикає колір усіх пікселів, що мають із $p$ спільну сторону (тобто його горизонтальних і вертикальних сусідів, але не діагональних). Тим не менш, при правильному виборі натискань кнопок можна відобразити бажане зображення.

Чи можливо отримати задане зображення? Якщо так, вкажіть спосіб це зробити.

Зауважте, що порядок натискань кнопок не впливає на результат, і немає потреби натискати одну й ту саму кнопку більше одного разу. Розв'язок визначається множиною натиснутих кнопок. Може існувати кілька правильних розв'язків — виведіть будь-який із них.

Вхідні дані

Перший рядок містить два цілих числа $k$ та $l (1 \leq k \times l \leq 1 0^{5})$ l~(1 \le k \times l \le 10^5).

Для кожного $i$ ( $0 \leq i < k$ 0 \le i < k), рядок $i + 2$ i+2 містить $l$ символів ( $B$ або $W$ ), розділених пробілами. Якщо $j$ -й символ ( $0 \leq j < l$ 0 \le j < l) дорівнює $B$ , то піксель у рядку $i$ та стовпці $j$ має бути чорним; інакше — білим.

Вихідні дані

Якщо отримати задане зображення неможливо, виведіть єдиний рядок IMPOSSIBLE.

Інакше виведіть $k$ рядків, кожен із яких містить $l$ символів ( $A$ або $P$ ), розділених пробілами:

Для всіх $i$ та $j$ ( $0 \leq i < k$ 0 \le i < k, $0 \leq j < l$ 0 \le j < l): якщо $j$ -й символ у рядку $i + 1$ i+1 дорівнює $P$ , то кнопку, що відповідає пікселю $(i, j)$ , необхідно натиснути; інакше — не натискати.

Приклади

Приклад 1

Приклад 2

Примітка

Пояснення до прикладу 1: щоразу, коли натискається кнопка, кольори обох пікселів змінюються одночасно. Тому вони завжди залишаються одного кольору, і бажане зображення отримати неможливо.

Пояснення до прикладу 2: якщо натиснути кнопки, що відповідають червоним пікселям на лівому зображенні, буде отримано зображення праворуч.