Cell Simulation / Conway's Game of Life

Problem: Cellular Grid Evolution

You receive a two-dimensional board with R rows and C columns. Every position contains one of the following values:

• 1: living
• 0: not living

Advance this board through T generations, then print the resulting configuration.

For any position, examine the eight surrounding locations and total how many of them are alive. Any neighbor that would fall beyond the board boundary counts as dead.

Rules:

1. When the cell is currently alive:
   • It becomes dead when it has under 2 living neighbors.
   • It remains alive when it has either 2 or 3 living neighbors.
   • It becomes dead when it has over 3 living neighbors.
2. When the cell is currently dead:
   • It turns alive when precisely 3 neighboring cells are alive.
   • In every other case, it stays dead.

Input Format

The opening line provides three integers:

R C T

Each of the following R lines is a binary string containing C characters and describes the starting board.

Output Format

Write R lines, with C characters per line, showing the board once T generations have been processed.

Constraints

• 1 <= R, C <= 200
• 0 <= T <= 100

Example

Input:

3 3 1
010
010
010

Output:

000
111
000

The three vertically aligned live cells produce a horizontal line after one generation.

Example

Input:
4 4 1
0000
0110
0110
0000

Output:
0000
0110
0110
0000

The central 2-by-2 group remains unchanged because each of its living cells has exactly three live neighbors.