In what concerns the continuous evaluation solving exercises grade during the semester, you should submit until 23:59 of December 20th
(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)

[IP098] Shifting Patterns

After everything he has been through, Will Byers has grown unusually perceptive about patterns, especially those that resemble the eerie shifts he can sense in the Upside Down. He has stumbled upon the Game of Life, a two-dimensional cellular automaton created by John Conway. Its cycles of emergence, collapse, and rebirth immediately catch his attention, reminding him of the strange rhythms he feels. Hoping to study and understand these dynamics more closely, Will decides to simulate the automaton and he needs your help.

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

In the grid, each cell can be empty or be occupied by an organism. 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 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 live 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.
• For the purposes of this problem, any neighbour cells "outside" the grid are considered as being dead.

The following figures illustrate an initial configuration of the game of life and the three consecutive generations that follow from it .

The Problem

Write a program that, given an initial configuration and a number K indicating the number of generations to simulate, produces and prints all the 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 C characters representing the initial state of the game. Dead cells are represented by '.' and live cells by '#'.

Output

You must print the K generations that follow the initial configuration.

Each generation should start by having a line with an integer indicating the generation number and then 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:

10 10 3
..........
....#.....
..#.#.....
...##.....
..........
..........
..........
..........
.....###..
..........

1
..........
...#......
....##....
...##.....
..........
..........
..........
......#...
......#...
......#...
2
..........
....#.....
.....#....
...###....
..........
..........
..........
..........
.....###..
..........
3
..........
..........
...#.#....
....##....
....#.....
..........
..........
......#...
......#...
......#...