Grid Game

An infinite grid is divided into unit square cells. Every cell is either alive or dead.

Every second all cells change state at the same time, by this rule.

• Take the five cells made of $C$ itself and the four cells that share an edge with $C$. If at least one of them is alive, then $C$ is alive one second later.
• Otherwise $C$ is dead one second later.

Given the starting state of the grid, write a program that counts how many cells are alive after $K$ seconds.

The first line contains the number of rows $N$ and the number of columns $M$ of the rectangular area whose starting state is given. ($1 \le N, M \le 50$)

Each of the next $N$ lines contains $M$ characters describing the starting state of that area. An alive cell is o and a dead cell is .. Every cell outside the area is dead at the start.

The last line contains $K$. ($1 \le K \le 1500$)

Print the number of alive cells after $K$ seconds.

Suppose the starting state is the one below and $K = 3$.

oo
o.

After 3 seconds the grid looks like this.

...oo...
..oooo..
.oooooo.
oooooooo
ooooooo.
.ooooo..
..ooo...
...o....