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