ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1229. Прочная кладка

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Problem illustration
Строителям нужно покрыть прямоугольную область размером 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