Республиканская олимпиада по информатике 2010 год, Кызылорда

Задача C. Игра

Ограничение по времени:

2 секунды

Ограничение по памяти:

256 мегабайт

Недавно Амир разработал новую игру. Она представляет собой поле из $N \times M$ клеток черного и белого цвета. При нажатии на клетку, все соседние с ней по стороне клетки меняют цвета на противоположный. Цель игры: из начальной раскраски поля получить заданную конечную раскраску. Ваша задача — выиграть, то есть определить, какие клетки и сколько раз нужно нажать, чтобы сделать это.

Формат входного файла

Первая строка входного файла содержит два целых числа $N$ и $M$ ($1 \le N, M \le 10$). Для удобства далее цвета обозначены цифрами: $1$ — черный, $2$ — белый. На следующих $N$ строках расположены по $M$ целых чисел в пределах от $1$ до $2$ — цвета соответствующих клеток поля в начальной раскраске. На следующих $N$ строках расположены по $M$ целых чисел в пределах от $1$ до $2$ — цвета соответствующих клеток поля в конечной раскраске. Числа в строках разделены пробелами.

Формат выходного файла

Если игру можно выиграть выведите $N$ строк по $M$ целых чисел от $0$ до $1$, разделенных пробелами — сколько раз нужно нажать соответствующую клетку. Если игру выиграть нельзя выведите \t{No solution}.

Пример:

Вход

2 2
2 1
1 2
1 1
1 1

Ответ

0 1
0 0