Description
The night breeze is cold; the past feels like a dream.
My heart is frozen; how can anyone bear knowing but not meeting?
It's hard to let go of the pain and the wind-like love.
Hard to forget you who roam yet in my heart.
I planted H x W roses for you in a gridded flower bed. Since the day we parted, the grid changed according to certain rules:
1. The blooming flower in a cell with 0 or 1 blooming neighbor withers due to loneliness.
2. The flower in a cell with 2 blooming neighbors stays the same, withered or blooming.
3. The withered flower in a cell with 3 blooming neighbors blooms due to the power of love.
4. The blooming flower in a cell with at least 4 blooming neighbors withers due to the competition.
Here, "neighbors of a cell" refers to the flowers in all cells around that certain cell, including diagonally connected ones. The cells at the corners and the edges have 3 and 5 neighbors respectively.
For example, suppose this was the bed before the breakup,
If we count the number of neighbors in each cell, we get:
Therefore, applying the rules to each cell, the new withered cells (dark green) and the new blooming cells (blue) are:
And the flower bed after the breakup is:
Given the initial flower configurations, output the flower bed after the breakup.
Input
The first line contains two numbers, H and W (1 <= H, W <= 256), representing the size of the flower bed.
The next H lines contain W numbers, 0 for the withered flowers and 1 for the blooming flower before the breakup.
Output
The flower bed after the breakup with a space after the numbers, including the last ones in each line.