E. Специальный граф
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

В этой задаче вам придется иметь дело с графом-сеткой размера n × m. Вершины этого графа — это узлы сетки n × m. Ребра этого графа — это все стороны и диагонали единичных квадратов сетки.

На рисунке ниже изображен граф размера 3 × 5. Черные линии изображают ребра графа, цветные кружочки изображают вершины графа. Вершины графа на рисунке раскрашены не просто так, раскраска является корректной вершинной раскраской графа размера 3 × 5 в четыре цвета. Раскраска называется корректной тогда и только тогда, когда каждая вершина покрашена, и никакие две вершины, соединенные ребром, не покрашены в один и тот же цвет.

Задан размер графа-сетки n × m, а также цвета некоторых его вершин. Найдите хотя бы один способ раскрасить вершины, цвета которых не заданы, в четыре цвета, чтобы итоговая раскраска являлась корректной вершинной раскраской. Если такого способа не существует, сообщите об этом.

Входные данные

В первой строке записаны два целых числа n и m (2 ≤ n, m ≤ 1000). В каждой из следующих n строк записано по m символов — заданный граф. Каждый символ — это один из символов: «0», «1», «2», «3», «4». Символ «0» обозначает, что цвет соответствующей вершины графа не задан, остальные символы обозначают, что вершина покрашена в заданный цвет.

Считайте, что цвета пронумерованы от 1 до 4.

Выходные данные

Если описанного способа не существует, в единственной строке выведите 0. Иначе выведите покрашенный граф размера n × m. Выводите граф в таком же формате, в котором он задан во входных данных.

Если существует несколько правильных ответов, разрешается вывести любой.

Примеры
Входные данные
3 5
10101
00020
01000
Выходные данные
13131
42424
31313
Входные данные
2 2
00
00
Выходные данные
12
34
Входные данные
2 2
11
00
Выходные данные
0
Примечание

В первом тестовом примере ответ совпадает с картинкой из условия (1 — зеленый цвет, 2 — голубой, 3 — синий, 4 — розовый).

На второй тестовый пример существует ровно 4! ответов, любой из них считается правильным.

В третьем тестовом примере в изначальной раскраске две вершины одного цвета соединены ребром. Значит нельзя дополнить такую раскраску до корректной.