Строителям нужно покрыть прямоугольную область размером M × N (M и N чётные) двумя слоями прямоугольных кирпичей размером 1 × 2. Первый слой кирпичей уже завершён. Второй слой (чтобы сделать кладку действительно прочной) должен быть выполнен так, что никакой кирпич не лежит целиком на кирпиче первого слоя.
По расположению кирпичей в первом слое определите возможное расположение кирпичей во втором слое или сообщите, что второй слой сделать невозможно.
Пример. Приведённые рисунки показывают расположение кирпичей в первом и втором слое. Размер области 2 × 4. Каждый кирпич помечен номером на обоих его половинках.
Исходные данные
N, M — размеры области. Затем следуют N строк, содержащих M чисел каждая. Эти строки описывают расположение кирпичей в первом слое. Каждый кирпич помечен двумя равными числами, записанными в квадратах области, покрываемых этим кирпичом. Все кирпичи помечены целыми числами в диапазоне от 1 до общего числа кирпичей. M и N — чётные числа, не превосходящие 100.
Результат
Если решения нет, выведите −1. Если решение существует, выведите N строк, содержащих M чисел каждая. Эти строки должны описывать расположение кирпичей во втором слое описанным выше способом.
Пример
исходные данные | результат |
---|
2 4
1 1 2 2
3 3 4 4 | 2 1 1 4
2 3 3 4 |
Источник задачи: Четвертьфинальные соревнования ACM ICPC 2002–2003 в центральном регионе России, Рыбинск, октябрь 2002