In what concerns the continuous evaluation solving exercises grade during the semester, you should submit until 23:59 of December 21st
(this exercise will still be available for submission after that deadline, but without couting towards your grade)
[to understand the context of this problem, you should read the class #10 exercise sheet]

In this problem you should read from the standard input using functions such as input() and you should write to the standard output using functions such as print()

(you are expected to read the class instructions, that will help you build a solution with structured programming and incremental development)

[IP094] Game of Life

Sasuke Uchiha, known for his analytical mind and relentless pursuit of knowledge, has stumbled upon the Game of Life, a two-dimensional cellular automaton devised by the mathematician John Conway. Intrigued by its resemblance to the cycles of growth and destruction he has observed in the world, Sasuke decides to study its dynamics. However, creating the simulation proves to be a challenge, and he seeks your assistance.

In the game of life, a grid of cells evolves over time based on a few simple rules. Sasuke wants to see how an initial grid changes over multiple generations.

In the grid each cell can be occupied by an organism or not. Occupied cells are said to be alive and unoccupied cells are said to be dead. In each generation, the cells that are alive change their state depending on the number of neighbouring cells that are alive according to the following following rules:

• A cell's neighbours are the 8 cells that touch it horizontally, vertically or diagonally.
• If a cell is alive and the number of living neighbouring cells is 0 or 1, then in the next generation the cell dies of loneliness.
• If a cell is alive and has 4 or more neighbouring cells that are also neighbouring cells, then in the next generation the cell dies of overpopulation.
• A living cell with 2 or 3 living neighbouring cells remains alive in the next generation.
• If a dead cell has exactly 3 living neighbouring cells, it changes to the state of a living cell in the next generation.
• All cell births and deaths take place simultaneously, i.e. the changes are based on the current state and never on the future state.

The following figures illustrate two consecutive states of a game of life configuration.

The Problem

Write a program that, given an initial state and number K indicating the number of generations to compute, produces the state obtained after K generations.

Input

The first line contains three positive integers: the number of rows R and columns C that determine the size of the grid and the number of iterations K it must perform.

This is followed by R lines of characters representing the initial state of the game. Dead cells are represented by '.' and live cells by '#'.

Output

You must print the state of the game after K iterations, i.e. R rows, each with C characters representing the game grid with the dead cells marked with '.' and the live cells with '#'.

Constraints

The following limits are guaranteed in all the test cases that will be given to your program:

5 5 5
.....
.....
.###.
.....
.....

.....
..#..
..#..
..#..
.....