Under construction

Still being built. Things may change

Life Game

Interview

Time limit2sMemory limit512 MB

Summary
Simulate Conway-style life on an N x M board for T steps using a (2K+1) square neighborhood with thresholds a and b, then print the final board.
Level

Medium6 of 10

Topics
Simulation, Implementation, Prefix sum, Array
Solved
No attempts yet

Problem

The Game of Life is a game invented by the mathematician John Horton Conway, in which 'life' is placed on a board-shaped grid and its changes are observed.

Junpyo modified a minor condition in the Game of Life invented by Conway and proposed a life game with new rules.

Each cell of the board is affected by its neighborhood, where the neighborhood means the region excluding the current cell from the square of side length (2K + 1) centered on the current cell, as in the colored area of <Figure 2>.

For each cell of the board, the next situation is determined as follows according to how many lives exist in its neighborhood.

  1. Survival : If the current cell has life and there are at least a and at most b lives in its neighborhood, the life in the current cell survives to the next step.
  2. Loneliness : If the current cell has life and there are fewer than a lives in its neighborhood, the life in the current cell dies of loneliness.
  3. Overpopulation : If the current cell has life and there are more than b lives in its neighborhood, the life in the current cell dies of overpopulation.
  4. Birth : If the current cell has no life and there are more than a and at most b lives in its neighborhood, life is born in the current cell at the next step.

Life cannot survive outside the board.

Junpyo scatters life on a board of size N×M and wants to observe the life after T hours.

Input

The first line gives two integers N and M, the vertical and horizontal lengths of the board, and the time T at which Junpyo wants to observe the board.

The second line gives the integer K, which is the criterion for the neighborhood, and the integers a and b, which determine the next situation of each cell.

Over the next N lines, the initial state of the board is given. Each line is a string of length M, where a cell with life is '*' and an empty cell is '.'.

Output

Over N lines, output the state of the board. Each line is a string of length M, where a cell with life is '*' and an empty cell is '.'.

Constraints

  • 1 ≤ N, M ≤ 100
  • 1 ≤ T ≤ 300
  • 0 ≤ a, b < (2×K+1)2

Examples1

  1. Example 1

    Input
    6 6 7
1 2 3
.*....
..*...
***...
......
......
......
    Expected output
    ......
......
..*...
...**.
..**..
......