题目描述

本题译自 eJOI2021 Problem C. Xcopy

今天，在程序设计课结束后，老师留了十分难的作业，所以孩子们决定作弊，抄别人的代码。然而，他们需要巧妙地配合，为了不让老师抓到抄袭。

班上有 $N\times M$ 个学生，他们坐在 $N$ 行 $M$ 列共 $N\times M$ 个位置上。当其中一个孩子坐在另一个孩子的前后左右四个相邻位置中的一个，我们认为这两个孩子是相邻的。作业是找到一个确定的非负整数。为了让他们不能互相抄袭，这些整数必须是不同的。同时，孩子们十分懒，因此它们抄别人的作业几乎不会进行修改。更确切地说，每个孩子的答案和任一相邻的孩子的答案在二进制下恰好有一位不同。例如 $3$ 和 $2$ 是恰好有一位不同的，但 $4$ 和 $2$ 不是。

孩子们不想引起老师怀疑，因此他们想让他们给出的最大的答案尽量小。给定 $N$ 和 $M$，请给出每个孩子的答案，使得老师不会发现孩子们抄袭。

输入格式

一行两个整数 $N$ 和 $M$，用一个空格隔开。

输出格式

输出对于孩子们的最优答案。输出应包含 $N$ 行，每行包含 $M$ 个用空格隔开的非负整数。这表示根据他们在班级坐的位置编排的答案。

注意：不符合输出格式（所有数都是不同的，并且两个相邻的数二进制表示中只有一位不同）的答案都会被对应测试点判为 $0$ 分。

3 3

5 4 6
1 0 2
9 8 10

在这部分中，一个数字的下标表示这个数字的进制。如十进制的 $8$ 会写为 $8_{10}=1000_{2}$。

一组学生给出的最优答案如下表所示：

$0101_{2}=5_{10}$	$0100_{2}=4_{10}$	$0110_{2}=6_{10}$
$0001_{2}=1_{10}$	$0000_{2}=0_{10}$	$0010_{2}=2_{10}$
$1001_{2}=9_{10}$	$1000_{2}=8_{10}$	$1010_{2}=10_{10}$

观察到任意两个相邻位置的数恰好有一位不同。这个解的最大值为 $10$，是最优解。显然有其他解同样也是最优的——水平或垂直翻转上表。

另一个可能的有部分分的解如下，最大值为 $15$。

$0110_{2}$	$0111_{2}$	$0101_{2}$
$1110_{2}$	$1111_{2}$	$1101_{2}$
$1010_{2}$	$1011_{2}$	$1001_{2}$

根据「数据范围与提示」一节的公式，这个解会被给这个测试点 $59.1\%$ 的分数。

数据范围与提示

• $1\le N,M\le 2000$

#	分值	限制
$1$	$7$	$N=1$
$2$	$9$	$N,M$ 是 $2$ 的幂次
$3$	$14$	$N$ 是 $2$ 的幂次
$4$	$70$	无附加限制

本题有部分分，分值取决于答案和最优答案相距多近。分值由如下公式计算：

$$S\cdot \max\left(1-\sqrt{\frac{\frac{G}{O}-1}{3}},0\right) $$

其中：

• $S$ 是每个测试点的分值
• $G$ 是选手给出的答案
• $O$ 是最优答案。