Gray Matrix Construction

Given two positive integers \(N\) and \(M\) such that the total number of cells \(N\times M\) is a power of two, construct an \(N \times M\) matrix \(A\) containing each integer from \(0\) to \(N\times M - 1\) exactly once. The matrix must satisfy the property that any two adjacent cells (neighbors in the four cardinal directions) have binary representations that differ in exactly one bit. Moreover, the maximum element in the matrix should be minimized (which will be \(N\times M - 1\)).

A valid construction is given by defining a function \[ G(x) = x \oplus (x \gg 1), \] where \(\oplus\) denotes bitwise XOR and \(x \gg 1\) is the right shift of \(x\) by one bit. Let \[ p = \log_2 M, \] (which is an integer since \(M\) is a power of two), then for \(0 \le i < N\) and \(0 \le j < M\), define \[ A[i][j] = (G(i) \ll p) \,|\, G(j), \] where \(\ll\) is the left shift operator and \(|\) is bitwise OR. It can be verified that adjacent cells differ in exactly one bit in their binary representation and that the maximum element is exactly \(N\times M - 1\).

Note: It is guaranteed that \(N\times M\) is a power of two.

inputFormat

The input consists of a single line containing two positive integers \(N\) and \(M\) separated by a space. It is guaranteed that \(N\times M\) is a power of two.

outputFormat

Output \(N\) lines, each containing \(M\) space-separated integers. The \(j\)-th number in the \(i\)-th line represents \(A[i][j]\) as constructed by the method above.

sample

2 2

0 1
2 3