В Японии очень популярны старые настольные игры на логику. Одна из таких игр проводится на доске размером $$$n \times m$$$.

В каждой позиции $$$(i, j)$$$, то есть на пересечении $$$i$$$-й сверху строки и $$$j$$$-го слева столбца, может находиться произвольное число фишек, которое мы обозначим за $$$a_{i, j}$$$. Правила самой игры довольно сложные: сложнее, чем шахматы, Го и Сёги, поэтому мы их не будем тут описывать целиком. Однако даже к стартовой расстановке фишек есть требования, про которые и будет эта задача.

Первое правило звучит следующим образом: к началу игры для любых двух соседних по стороне клеток суммарное число фишек в них должно быть нечётным. Более формально, если выполняется $$$|i_1-i_1| + |j_1-j_2| = 1$$$, то должно выполняться условие, что $$$a_{i_1, j_1} + a_{i_2, j_2}$$$ — нечётное число.

Вам дано текущее состояние доски, описанное матрицей текущих значений $$$a_{i, j}$$$. Первый игрок за одно действие может добавить ровно одну фишку на любую клетку поля. Причем у первого игрока будет тем больше преимущество,

• чем меньше суммарное число фишек на поле после его действий;
• а при равенстве общего числа фишек — чем лексикографически меньше итоговая матрица $$$a_{i, j}$$$.

Напомним, что матрица $$$X$$$ лексикографически меньше матрицы $$$Y$$$, если после записи каждой из матриц в одну строку (по строкам, сначала выписав первую, затем вторую, и так далее), в первой позиции, где они различаются, в записи матрицы $$$X$$$ стоит меньшее число.

Требуется добиться выполнения требуемого правила, добившись наиболее выгодной для первого игрока стартовой позиции. После внесения изменений выведите итоговую таблицу значений $$$a_{i, j}$$$.

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