Conway's Game of Life

You are given an initial state of a grid for Conway's Game of Life and a number of generations to simulate. The grid consists of cells that are either live (1) or dead (0). At each generation, the state of the grid is updated as follows:

• A live cell with fewer than 2 or more than 3 live neighbors dies.
• A live cell with 2 or 3 live neighbors remains alive.
• A dead cell with exactly 3 live neighbors becomes a live cell.

The neighbor relation is defined for the eight adjacent cells. Mathematically, if we denote the current state of a cell as \(c_{ij}\) and the number of live neighbors as \(N(c_{ij})\), then:

$$ \text{Next state of } c_{ij} = \begin{cases} 1, & \text{if } c_{ij} = 1 \text{ and } 2 \leq N(c_{ij}) \leq 3, \\ 1, & \text{if } c_{ij} = 0 \text{ and } N(c_{ij}) = 3, \\ 0, & \text{otherwise.} \end{cases} $$

Your task is to simulate this process for a given number of generations and output the final state of the grid.

inputFormat

The input is given via standard input (stdin) in the following format:

• The first line contains two positive integers (n) and (m) representing the number of rows and columns of the grid.
• Each of the next (n) lines contains (m) integers (0 or 1) separated by spaces, representing the grid's initial state.
• The last line contains a non-negative integer (g) representing the number of generations to simulate.

outputFormat

Output the final state of the grid after (g) generations. Each row should be printed on a new line with the cell values separated by a single space. The output should be sent to standard output (stdout).## sample

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

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

</p>