Строителям нужно покрыть прямоугольную область размером M × N (M и N чётные) двумя слоями прямоугольных кирпичей размером 1 × 2. Первый слой кирпичей уже завершён. Второй слой (чтобы сделать кладку действительно прочной) должен быть выполнен так, что никакой кирпич не лежит целиком на кирпиче первого слоя.

По расположению кирпичей в первом слое определите возможное расположение кирпичей во втором слое или сообщите, что второй слой сделать невозможно.

Пример. Приведённые рисунки показывают расположение кирпичей в первом и втором слое. Размер области 2 × 4. Каждый кирпич помечен номером на обоих его половинках.

N, M — размеры области. Затем следуют N строк, содержащих M чисел каждая. Эти строки описывают расположение кирпичей в первом слое. Каждый кирпич помечен двумя равными числами, записанными в квадратах области, покрываемых этим кирпичом. Все кирпичи помечены целыми числами в диапазоне от 1 до общего числа кирпичей. M и N — чётные числа, не превосходящие 100.

Если решения нет, выведите −1. Если решение существует, выведите N строк, содержащих M чисел каждая. Эти строки должны описывать расположение кирпичей во втором слое описанным выше способом.