В этой задаче вам придется иметь дело с графом-сеткой размера n × m. Вершины этого графа — это узлы сетки n × m. Ребра этого графа — это все стороны и диагонали единичных квадратов сетки.
На рисунке ниже изображен граф размера 3 × 5. Черные линии изображают ребра графа, цветные кружочки изображают вершины графа. Вершины графа на рисунке раскрашены не просто так, раскраска является корректной вершинной раскраской графа размера 3 × 5 в четыре цвета. Раскраска называется корректной тогда и только тогда, когда каждая вершина покрашена, и никакие две вершины, соединенные ребром, не покрашены в один и тот же цвет.
Задан размер графа-сетки n × m, а также цвета некоторых его вершин. Найдите хотя бы один способ раскрасить вершины, цвета которых не заданы, в четыре цвета, чтобы итоговая раскраска являлась корректной вершинной раскраской. Если такого способа не существует, сообщите об этом.
Выходные данные
Если описанного способа не существует, в единственной строке выведите 0. Иначе выведите покрашенный граф размера n × m. Выводите граф в таком же формате, в котором он задан во входных данных.
Если существует несколько правильных ответов, разрешается вывести любой.
Примечание
В первом тестовом примере ответ совпадает с картинкой из условия (1 — зеленый цвет, 2 — голубой, 3 — синий, 4 — розовый).
На второй тестовый пример существует ровно 4! ответов, любой из них считается правильным.
В третьем тестовом примере в изначальной раскраске две вершины одного цвета соединены ребром. Значит нельзя дополнить такую раскраску до корректной.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 5
10101
00020
01000
|
13131
42424
31313
|
|
2
|
2 2
00
00
|
12
34
|
|
3
|
2 2
11
00
|
0
|