Problem Description

Given positive integers $N, M$.

Please construct an $N \times M$ matrix containing only non-negative integers, such that all elements are pairwise distinct, and any two adjacent (up, down, left, right) elements differ in exactly one bit in binary. Also, make the maximum element in the matrix as small as possible.

Input Format

One line with two positive integers $N, M$.

Output Format

Output an $N \times M$ matrix containing only non-negative integers. The Special Judge is very strict about the output format: there must be no extra characters such as spaces at the end of each line.

3 3

5 4 6
1 0 2
9 8 10

Hint

Scoring Rules

This problem uses partial scoring. The score depends on the size of your output answer compared with the correct answer. Here, “answer” means the maximum element in the matrix.

Let $S$ be the full score of this test point, and $O$ be the correct answer. If $G$ is your output answer, then the score is:

$$S \times \max(1-\sqrt{\dfrac{\frac{G}{O}-1}{3}},0)$$

Because of Luogu’s scoring mechanism, the actual score for each test point is the floor of the above value, i.e. $\lfloor S \times \max(1-\sqrt{\dfrac{\frac{G}{O}-1}{3}},0) \rfloor$. For example, when $S=7, G=15, O=10$, the score by the formula is about $4.14$, but on Luogu the score is $4$.

If the output matrix does not meet the requirements (i.e. all elements are distinct and any two adjacent elements differ by exactly one bit in binary), then this test point gets $0$ points.

Note that, since the Special Judge has strict formatting requirements, please do not add extra spaces at the end of each line when printing your answer, otherwise the corresponding test point will be scored as $0$. Also, please do not output integers outside the range $[0,2^{63})$ (long long), otherwise it will be judged as a format error and scored as $0$.

Sample Explanation

The sample matrix is:

$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}$

It is easy to see that every pair of adjacent elements differs by exactly one bit in binary. The answer of this construction is $10$ (i.e. the maximum element), and it is the smallest among all valid constructions. Of course, other matrices with maximum element $10$ are also valid (for example, by flipping the matrix, etc.).

A construction that can get partial points is:

$0110_2$	$0111_2$	$0101_2$
$1110_2$	$1111_2$	$1101_2$
$1010_2$	$1011_2$	$1001_2$

The maximum element of this matrix is $15$. According to the scoring rules, before flooring it can get $\max(1-\sqrt{\dfrac{\frac{15}{10}-1}{3}},0)=1-\dfrac{\sqrt{6}}{6} \approx 59\%$ of the score for this test point.

Constraints and Notes

This problem uses bundled testdata.

• Subtask 1 (7 pts): $N=1$.
• Subtask 2 (9 pts): $N, M$ are integer powers of $2$.
• Subtask 3 (14 pts): $N$ is an integer power of $2$.
• Subtask 4 (70 pts): no special restrictions.

For $100\%$ of the data, $1 \le N, M \le 2000$.

Notes

This problem is translated from eJOI2021 Day 1 C XCopy. You are welcome to hack the self-written Special Judge via private messages or forum posts.

Translated by ChatGPT 5