Перевернути плитку
Фермер Джон знає, що інтелектуально задоволена корова - це щаслива корова, яка буде давати більше молока. Він організував для корів інтелектуальну гру, в якій вони маніпулюють набором з m * n квадратних плиток, кожна з яких пофарбована в чорний колір з одного боку і в білий колір з іншого.
Як можна здогадатися, при перевертанні біла плитка стає чорною, а чорна плитка стає білою. Корови отримають винагороду, якщо всі плитки будуть перевернуті білою стороною вгору. Однак у корів досить великі копита, і коли вони намагаються перевернути певну плитку, вони також перевертають всі сусідні плитки (ті, що мають спільну сторону з перевернутою). Оскільки перевертання втомлює, корови хочуть звести до мінімуму їх кількість.
Допоможіть коровам визначити мінімальну кількість перевертань і місця, які потрібно перевернути, щоб досягти цього мінімуму. Якщо існує декілька способів виконати завдання з мінімальною кількістю перевертань, виведіть той, який має найменший лексикографічний порядок, якщо розглядати його як рядок. Якщо завдання неможливе, виведіть слово "IMPOSSIBLE".
Вхідні дані
Перший рядок містить два цілих числа m і n (1 ≤ m ≤ 15, 1 ≤ n ≤ 15). Кожен з наступних m рядків описує кольори (зліва направо) рядка i сітки з n цілими числами: 1 - чорний, 0 - білий.
Вихідні дані
Виведіть m рядків. Кожен рядок містить n цілих чисел, кожне з яких вказує, скільки разів слід перевернути це конкретне місце.