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

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

Ограничение по времени Ограничение по памяти
2 секунды 256 мегабайт

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

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

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

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

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

Примеры

Вход

2 2
2 1
1 2
1 1
1 1

Выход

0 4
0 0