<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

249. Matrix
time limit per test: 0.5 sec.
memory limit per test: 65536 KB
input: standard
output: standard



It is necessary to arrange numbers from 0 to 2^(N+M)-1 in the matrix with 2^N rows and 2^M columns. Moreover, numbers occupying two adjacent cells must differ only in single bit in binary notation. Cells are adjacent if they have common side. Matrix is cyclic, i.e. for each row the leftmost and rightmost matrix cells are considered to be adjacent (the topmost and the bottommost matrix cells are also adjacent).

Input
The first line of input contains two integers N and M (0<N,M; N+M<=20).

Output
Output file must contain the required matrix in a form of 2^N lines of 2^M integers each.

Sample test(s)

Input
1 1

Output
0 2
1 3
Author:	Antony Popovich
Resource:	Petrozavodsk Summer Training Sessions 2004
Date:	August 25, 2004

<|response|>
1. Abridged Problem Statement  
Given positive integers N and M with N+M ≤ 20, build a 2^N × 2^M toroidal grid (rows and columns wrap around) containing each integer 0…2^(N+M)–1 exactly once, so that any two orthogonally adjacent cells differ in exactly one bit of their binary labels.

2. Key Observations  
- A cyclic N-bit Gray code is a sequence of length 2^N in which consecutive values (including the last to the first) differ by one bit.  
- If we label rows by an N-bit Gray code (upper bits) and columns by an M-bit Gray code (lower bits), then moving vertically flips exactly one of the upper N bits, and moving horizontally flips exactly one of the lower M bits. Wrap-around also flips exactly one bit.  
- Concatenating an N-bit code x and an M-bit code y into (x<<M)|y gives a unique (N+M)-bit label covering 0…2^(N+M)–1.

3. Full Solution Approach  
a. Generate G_N, the cyclic N-bit Gray code sequence of length 2^N, by G_N[i] = i ^ (i>>1) for i=0…2^N−1.  
b. Generate G_M similarly for M bits.  
c. Allocate a matrix with 2^N rows and 2^M columns. For each row index i and column index j, set  
   label = (G_N[i] << M) | G_M[j]  
   and print it.  
This guarantees that horizontally adjacent cells differ by the single bit that changes in G_M, vertically by the single bit in G_N, and wrap-around edges work the same way.

4. C++ Implementation with Detailed Comments  
```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n, m;

void read() { cin >> n >> m; }

vector<int> gray_code(int bits) {
    vector<int> res;
    for(int i = 0; i < (1 << bits); i++) {
        res.push_back(i ^ (i >> 1));
    }

    return res;
}

void solve() {
    // We want a 2^N x 2^M cyclic Gray arrangement of 0..2^(N+M)-1 where adjacent
    // cells differ in one bit. Take the standard reflected Gray code over N bits
    // for the rows and over M bits for the columns. Each Gray sequence is cyclic
    // (its first and last entries also differ in one bit), so wrapping the grid
    // is fine. The cell at row i, column j gets the high N bits from the row's
    // Gray value and the low M bits from the column's: (gn[i] << M) | gm[j].
    // Horizontal neighbours change only the column part by one bit and vertical
    // neighbours only the row part, so any two adjacent cells differ in exactly
    // one bit.

    vector<int> gn = gray_code(n), gm = gray_code(m);
    for(int i = 0; i < (int)gn.size(); i++) {
        for(int j = 0; j < (int)gm.size(); j++) {
            cout << (gn[i] << m) + gm[j] << ' ';
        }

        cout << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

5. Python Implementation with Detailed Comments  
```python
import sys

def gray_code(n):
    """
    Return the cyclic n-bit Gray code sequence of length 2^n.
    The i-th Gray code is i ^ (i>>1).
    """
    return [i ^ (i >> 1) for i in range(1 << n)]

def main():
    data = sys.stdin.read().split()
    N, M = map(int, data[:2])

    # Generate Gray codes for rows and columns
    G_N = gray_code(N)
    G_M = gray_code(M)

    # Build and print the matrix
    # Each row i: (G_N[i] << M) | G_M[j] for j in 0..2^M-1
    R, C = 1 << N, 1 << M
    out = []
    for i in range(R):
        row_code = G_N[i]
        # compute one entire row by combining with all G_M entries
        row = [(row_code << M) | gm for gm in G_M]
        out.append(" ".join(map(str, row)))
    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()
```