In some cells of the square \( N\ х\ N\) microorganisms live (no more than one in one cell). The following happens every second:
– all microorganisms that have less than 2 neighbors die of boredom (neighbors are microorganisms that live in cells that have a common side or top);
– all microorganisms with more than 3 neighbors die from overcrowding;
– on all empty cells, in which microorganisms lived in exactly three adjacent cells, new microorganisms appear.
All changes occur simultaneously, that is, for each cell, its fate is first clarified, and then changes occur in all cells at once.
It is required to determine from this configuration what it will turn into after \(T\) seconds.
Input data: The first line contains two natural numbers –
\( N\) (
\(1 \leq N \leq 10\)) and
\(T\) (
\(1 \leq T \leq 100\)). Next,
\( N\) lines of
\( N\) numbers, describing the initial configuration (0 – empty cell, 1 – microorganism). Numbers in lines are separated by spaces.
Output: Required to output
\( N\) lines by
\( N\) numbers – a description of the configuration in T seconds (in the same format as in the input data).
Examples
| # |
Input |
Output |
| 1 |
3 1
1 0 1
1 0 1
1 0 1
| 0 0 0
1 0 1
0 0 0
|
| 2 |
2 2
1 1
1 1
| 1 1
1 1
|
| 3 |
5 10
1 0 1 1 0
0 1 0 0 0
0 0 0 1 0
0 0 0 0 0
0 1 0 1 0
| 0 1 1 0 0
0 1 1 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
|