Conway's Game of Life Simulation

In this problem, you are given the current state of a grid in Conway's Game of Life. Your task is to compute the next state of the grid based on the following rules:

• Underpopulation: A live cell with fewer than two live neighbors dies.
• Survival: A live cell with two or three live neighbors lives on to the next generation.
• Overpopulation: A live cell with more than three live neighbors dies.
• Reproduction: A dead cell with exactly three live neighbors becomes a live cell.

Mathematically, if we denote the number of live neighbors by \(n\) and the current state by \(s\), then the rules can be summarized as follows:

• If \(s=1\) and (\(n 3\)), then the cell becomes 0 (dies).
• If \(s=1\) and (\(n = 2\) or \(n = 3\)), then the cell remains 1 (lives).
• If \(s=0\) and \(n = 3\), then the cell becomes 1 (reproduces).

You will be given the size of the grid and the initial configuration. Compute and output the next state of the grid.

inputFormat

The first line contains two integers N and M representing the number of rows and columns respectively. Each of the next N lines contains M space-separated integers (either 0 or 1) indicating the initial state of each cell in the grid.

outputFormat

Output the next state of the grid in the same format: N lines with M space-separated integers on each line.## sample

4 3
0 1 0
0 0 1
1 1 1
0 0 0

0 0 0
1 0 1
0 1 1
0 1 0