Conway's Game of Life: Next State Computation

In this problem, you are given a finite grid representing the current state of cells in Conway's Game of Life. A cell can be either alive (denoted by 1) or dead (denoted by 0). The evolution of the grid is determined by the following rules:

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

The neighbor count is calculated over the eight adjacent cells. Mathematically, for each cell at position \( (i,j) \), the number of live neighbors is given by:

\( N(i,j) = \sum_{di=-1}^{1}\sum_{dj=-1}^{1} \textbf{1}_{[(di,dj) \neq (0,0)]} \cdot grid[i+di][j+dj] \)

Your task is to compute and output the next state of the grid after applying these rules simultaneously to every cell.

inputFormat

The first line contains two integers R and C, representing the number of rows and columns of the grid respectively. This is followed by R lines, each containing C integers (0 or 1) separated by spaces, representing the current state of the grid.

outputFormat

Output the next state of the grid in the same format, with R lines where each line contains C integers separated by a single space.## sample

3 3
0 1 0
0 1 0
0 1 0

0 0 0
1 1 1
0 0 0