题目描述

给定正整数 $N,M$。

请构造一个 $N \times M$ 的只包含非负整数的矩阵，使得每个元素互不相同且相邻（上下左右）元素在二进制下只有一位不同，同时保证矩阵的最大元素最小。

输入格式

一行两个正整数 $N,M$。

输出格式

一个 $N \times M$ 的只包含非负整数的矩阵。Special Judge 对输出格式要求非常严格，每行行末不能有空格等多余字符。

3 3

5 4 6
1 0 2
9 8 10

提示

评分规则

本题采用部分分计分，分数取决于输出答案和正确答案的大小。其中「答案」指的是矩阵中的最大元素。

设 $S$ 为该测试点的总分，$O$ 为正确答案。那么当 $G$ 为输出答案时，得分为：

由于洛谷评分机制，每个测试点的实际得分为上式下取整的结果，即 $\lfloor S \times \max(1-\sqrt{\dfrac{\frac{G}{O}-1}{3}},0) \rfloor$。例如，当 $S=7,G=15,O=10$ 时，按上式得分约为 $4.14$ ，但在洛谷上得分为 $4$。

如果输出矩阵不满足要求（即元素互不相同且相邻元素在二进制下只有一位不同），那么该测试点计 $0$ 分。

注意，由于 Special Judge 对于格式要求较高，请在输出答案时不要在每行末尾添加多余空格，否则对应测试点会被计为 $0$ 分。另外，请不要输出超出 $[0,2^{63})$ 范围（long long）的整数，否则会被判为格式错误，计 $0$ 分。

样例解释

样例矩阵如下：

通过观察不难发现，每两个相邻元素在二进制下都只有一位不同。这种做法的答案为 $10$（即最大元素），是所有做法中最小的。当然，其它的最大元素为 $10$ 的矩阵也是符合题意的（例如将输入矩阵进行翻转操作等）。

一种可以获得部分分的做法是：

该矩阵的最大元素为 $15$。根据评分规则，这种做法在下取整前可以获得对应测试点 $\max(1-\sqrt{\dfrac{\frac{15}{10}-1}{3}},0)=1-\dfrac{\sqrt{6}}{6} \approx 59\%$ 的分数。

数据规模与约定

本题采用捆绑测试。

• Subtask 1（7 pts）：$N=1$。
• Subtask 2（9 pts）：$N,M$ 是 $2$ 的整数幂。
• Subtask 3（14 pts）：$N$ 是 $2$ 的整数幂。
• Subtask 4（70 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le N,M \le 2000$。

说明

本题译自 eJOI2021 Day 1 C XCopy。欢迎通过私信或发帖的方式对自行编写的 Special Judge 进行 hack。