Bees

Bees store honey in a honeycomb every day. The honeycomb is a grid of regular hexagonal cells arranged in rows and columns. During the night the larvae eat all of the honey, so the honeycomb is completely empty when a day begins. The bees do not pick cells at random. Which cells receive honey is decided by which cells held honey on the previous day. A cell holds honey exactly when the number of its neighboring cells that held honey on the previous day is odd, and it stays empty otherwise. A cell is not its own neighbor.

Two adjacent rows are offset by half a cell. The first cell of row 1 sits above and to the left of the first cell of row 2. The neighbors of the cell in row $i$ and column $j$ are therefore:

• $(i, j-1)$ and $(i, j+1)$ in the same row
• $(i-1, j-1)$, $(i-1, j)$, $(i+1, j-1)$, $(i+1, j)$ when $i$ is odd
• $(i-1, j)$, $(i-1, j+1)$, $(i+1, j)$, $(i+1, j+1)$ when $i$ is even

Positions outside the honeycomb are not neighbors.

The picture shows the honeycomb of the first example input.

The first line contains three natural numbers $n$, $m$ and $k$ separated by spaces ($2 \le n, m \le 10$, $1 \le k \le 2^{63} - 1$). Here $n$ is the number of rows of the honeycomb, $m$ is the number of columns, and $k$ is the number of days that pass.

Each of the next $n$ lines contains $m$ characters. A '#' means the cell holds honey at the start, and a '.' means it does not.

Print the state of the honeycomb after $k$ days in $n$ lines, in the same format as the input.