Древняя игра（远古游戏）

题目描述

在日本，古老的逻辑棋盘游戏非常流行。其中一种游戏在大小为 $n \times m$ 的棋盘上进行。

在每个位置 $(i, j)$，即从上数第 $i$ 行、从左数第 $j$ 列的交点处，可以放置任意数量的棋子，记作 $a_{i, j}$。游戏规则相当复杂，比国际象棋、围棋和将棋还要难，因此这里不完整叙述。但是，即使对于起始棋子的布局，也有一些要求，本题正是关于这些要求。

第一个规则如下：游戏开始时，对于任意两个相邻（有公共边）的格子，其中棋子的总数必须为奇数。更形式化地说，如果满足 $|i_1-i_1| + |j_1-j_2| = 1$（原文如此，应为 $|i_1-i_2| + |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}$。

输入格式

第一行包含两个整数 $n$ 和 $m$，表示棋盘尺寸（$1 \le n, m \le 100$）。

接下来 $n$ 行，每行包含 $m$ 个整数，第 $i$ 行第 $j$ 个数为 $a_{i, j}$，表示格子 $(i, j)$ 中的初始棋子数量（$0 \le a_{i, j} \le 10^9$）。

输出格式

输出 $n$ 行，每行 $m$ 个整数，表示最终的 $a_{i, j}$ 表格。

要求：棋子总数尽可能小；对于任意相邻（有公共边）的格子，其数值之和必须为奇数；在满足上述条件的所有方案中，最终矩阵的字典序最小。

评分标准

每个子任务的得分仅在通过该子任务所有测试点以及所需前置子任务的所有测试点后才能获得。

样例

输入

2 3
1 1 2
2 2 3

输出

2 1 2
3 2 3