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

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

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

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

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

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

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

Примеры

Вход

2 2
2 1
1 2
1 1
1 1

Выход

0 4
0 0