XCopy

시간 제한2초메모리 제한1024 MB

요약

N 곱하기 M 격자의 각 칸에 서로 다른 정수를 배정하되 이웃한 칸끼리 정확히 한 비트만 다르고 최댓값이 최소가 되도록 한다.

난이도: 보통10점 중 7점
유형: 비트 연산, 수학, 구현
정답자: 아직 제출이 없습니다

문제

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 in order to not get caught cheating.

The class has $N \times M$ students, placed in $N \times M$ benches on $N$ rows and $M$ columns. Two children are considered neighbours if one sits in a bench adjacent to the left, the right, above or below the bench in which the other one sits. The homework consists of finding a certain non-negative integer. In order for them to not get caught cheating, all these integers must be different. Also, the children are very lazy, therefore they will barely modify their answers when copying them from their neighbours. More precisely, each child’s answer differs by exactly one bit in base $2$ compared to any of his neighbours’ answers. For example $3$ and $2$ differ in exactly one bit, whereas $2$ and $4$ do not.

The children don’t want to raise suspicion, therefore they want the largest answer that any of them gave to be as small as possible. Given $N$ and $M$ , create a configuration of answers so that the teacher won’t find out the children cheated.

입력

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

출력

The output consists of the optimal answers for the children. The output should have $N$ rows, each containing $M$ non-negative integers separated by a single space. These represent the answers for the children, according to where they sit in the class.

제한

$1 ≤ N, M ≤ 2000$

힌트

Within this section, a subscript after a number represents the base in which the number is written. For instance eight may be written as $8\_{10} = 1000\_2$ .

One set of optimal answers for the students are given in the following table:


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

Observe that between any two adjacent benches the numbers differ with exactly one bit. The maximum value of the solution is $10$ , which is the optimal answer. Clearly other solutions are optimal – such as the previous solution but flipped vertically or horizontally.

Another possible partial solution in which the maximum is $15$ is:


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

This solution would be scored, according to the scoring formula, with $59.1\\%$ of the test case score.

예제1

예제 1
입력
```
3 3
```
예상 출력
```
5 4 6
1 0 2
9 8 10
```