DMPG '17 S5 - Bit Matrix

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type

Ruby likes binary numbers. She also likes matrices. Therefore, she definitely likes matrices filled with binary numbers!

After thinking about them for a while, she comes up with an interesting question:

Given integers N and M, find an N \times M matrix of distinct numbers, where each number in the matrix differs by exactly one bit from its adjacent (up, down, left, right) numbers in the matrix.

Since Ruby knows you like matrices and binary numbers just as much as she does, she's challenged you to solve her problem!

Input Specification

The first and only line of input will contain two space-separated integers N and M (1 \le N, M \le 1024).

Output Specification

An N \times M matrix that satisfies the properties given above, outputted as N lines of M space-separated decimal integers that must be smaller than 2^{31} - 1. There may be multiple solutions, in which case you may output any of them.

Sample Input

3 5

Sample Output

0 2 10 8 24
1 3 11 9 25
5 7 15 13 29

Explanation

When seen in binary, it is apparent that each cell differs by only one bit from its adjacent cells. Wow! How cool is that?

00000 00010 01010 01000 11000
00001 00011 01011 01001 11001
00101 00111 01111 01101 11101