Conway's Game of Life: Next State Computation

In this problem, you are given the current state of a board for Conway's Game of Life. The board is represented as a 2D grid with cells that are either alive (1) or dead (0). Your task is to compute the next state of the board based on the following rules:

(\textbf{Rules:})

1. Any live cell with fewer than 2 live neighbors dies, as if by underpopulation.
2. Any live cell with 2 or 3 live neighbors lives on to the next generation.
3. Any live cell with more than 3 live neighbors dies, as if by overpopulation.
4. Any dead cell with exactly 3 live neighbors becomes a live cell, as if by reproduction.

Input is read from standard input (stdin) and output is written to standard output (stdout). The board dimensions and cell states are provided, and your program should print the board's next state in the same format.

Be careful to consider the boundaries of the board. Use efficient iteration, especially if the board is large. Good luck!

inputFormat

The first line of input contains two integers (N) and (M), representing the number of rows and columns of the board. This is followed by (N) lines, each containing (M) integers separated by space. Each integer is either 0 or 1, where 0 represents a dead cell and 1 represents a live cell.

outputFormat

Output the next state of the board in the same format: (N) lines where each line contains (M) integers separated by a single space. Each integer should be either 0 or 1, representing the state of the cell in the next generation.## sample

3 3
0 0 0
0 1 0
0 0 0

0 0 0
0 0 0
0 0 0