Conway's Game of Life: Next Generation

You are given an initial configuration of Conway's Game of Life on a two-dimensional grid. Your task is to compute the next generation of the grid based on the following rules:

• A live cell with fewer than \(2\) live neighbors dies due to underpopulation.
• A live cell with \(2\) or \(3\) live neighbors lives on into the next generation.
• A live cell with more than \(3\) live neighbors dies due to overpopulation.
• A dead cell with exactly \(3\) live neighbors becomes a live cell due to reproduction.

The grid is represented as \(r \times c\) matrix of integers where a \(1\) represents a live cell and a \(0\) represents a dead cell. The update is applied simultaneously to every cell in the grid.

For example, given the input grid:

0 1 0
0 0 1
1 1 1

The next generation would be:

0 0 0
1 0 1
0 1 1

inputFormat

The first line of input contains two space-separated integers \(r\) and \(c\) representing the number of rows and columns of the grid. The following \(r\) lines each contain \(c\) space-separated integers (either 0 or 1) representing the initial state of the grid.

Example:

3 3
0 1 0
0 0 1
1 1 1

outputFormat

Output the next generation of the grid in the same format as the input grid. Each row should be printed on a new line with cells separated by a single space.

Example:

0 0 0
1 0 1
0 1 1

## sample

3 3
0 1 0
0 0 1
1 1 1

0 0 0
1 0 1
0 1 1

</p>