XCopy

Time limit2sMemory limit1024 MB

Summary

Assign distinct non-negative integers to each cell of an N by M grid so that neighboring cells differ by exactly one bit, minimizing the largest value used.

Level: Hard8 of 10
Topics: Bit manipulation, Matrix, Implementation
Solved: No attempts yet

Problem

Today, at the end of the programming class, the teacher gave very difficult homework, so the children decided to cheat and copy it from one another. However, they have to work smart so they do not get caught.

The class has $N \times M$ students seated at $N \times M$ benches arranged in $N$ rows and $M$ columns. Two children are neighbors if one sits at a bench directly to the left, right, above, or below the other. The homework asks for a non-negative integer. To avoid getting caught, all these integers must be different. The children are also lazy, so each child's answer differs from each neighbor's answer by exactly one bit in base $2$ . For example, $3$ and $2$ differ in exactly one bit, but $2$ and $4$ do not.

The children want the largest answer any of them gave to be as small as possible. Given $N$ and $M$ , create an arrangement of answers so that the teacher will not find out the children cheated.

Input

The input consists of $N$ and $M$ on a single line, separated by a single space.

Output

Print the optimal answers. Print $N$ rows, each containing $M$ non-negative integers separated by single spaces. Each integer is the answer of the child sitting at that position.

Constraints

$1 \le N, M \le 2000$

Hint

In this section, a subscript after a number gives the base in which the number is written. For example, eight is written $8_{10} = 1000_2$ .

One set of optimal answers is shown in the table below:

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

Adjacent benches always have numbers that differ in exactly one bit. The maximum value of this solution is $10$ , which is optimal. Other optimal solutions also exist, such as this one flipped vertically or horizontally.

Another partial solution has a maximum of $15$ :

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

Under the scoring formula, this solution would receive $59.1\%$ of the test case score.

Examples1

Example 1
Input
```
3 3
```
Expected output
```
5 4 6
1 0 2
9 8 10
```