407702: GYM102878 D Life Game

Scientists try to figure out how does the initial biosphere look like. So they design an experiment with serval micro-creatures in a matrix grid and observe their behavior.

A grid point can exist at most $$$1$$$ micro-creature and there are only two states of their life activities, which are * for alive and . for death.

At each time point, all the micro-creatures will transfer between two states. And the transformation will only depend on states of the 8 micro-creatures around it.

Let l, r $$$(0 \leq l \leq r \leq 8)$$$ be the suitable living range of the micro-creatures. Only if the number of alive micro-creatures around it is not greater than r and not less than l, the creature will become or keep alive, otherwise it will keep death or die due to overcrowding or loneliness.

Now, you are given the initial state of the micro-creatures in a matrix grid, please predict what will be them looked like after a while.

The first line gives two integers $$$n, m (1 \leq n, m \leq 100)$$$, which means that there are $$$n * m$$$ grids on the matrix grid, guarantee that

The second line gives two integers $$$l, r (0 \leq l \leq r \leq 8 )$$$, which represents that it is suitable for survival when the number of living creatures around the creature is $$$[l, r]$$$ .

The third line gives only one integer $$$t (1 \leq t \leq 10^3)$$$, which means that the time point you should predict.

In the next $$$n$$$ line, each line gives $$$m$$$ characters "*" or "." to represent there is life or no life on the grid in the initial state.

A matrix of $$$n \times m$$$ composed of "*" and "." to represent the state at the time $$$t$$$. Please notiece that the initial state is considered as time 1.

5 5
2 3
8
*...*
.*.*.
..*..
.*.*.
*...*

.....
.....
.....
.....
.....

5 5
3 6
8
*...*
.*.*.
..*..
.*.*.
*...*

*****
*...*
*...*
*...*
*****

The evolution of case 1 is as follows:

It will finally stop in the last state.

The evolution of case 2 is as follows:

Finally it loops through the three states.