L. Game of Life
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given a board of size $$$N \times N$$$, where each cell can be alive, dead, or uninhabitable, simulate the evolution of the board for $$$K$$$ iterations based on the following rules:

$$$\bullet$$$ A live cell ($$$\texttt{'1'}$$$) dies if it has an odd number of live neighbors.

$$$\bullet$$$ A dead cell ($$$\texttt{'0'}$$$) becomes alive if it has an odd number of live neighbors.

$$$\bullet$$$ An uninhabitable cell ($$$\texttt{'#'}$$$) never changes state and is never considered alive.

Each cell has up to 8 neighbors (horizontal, vertical, and diagonal).

Your goal is to determine the final state of the board after $$$K$$$ iterations.

Input

The first line contains two integers $$$N$$$ and $$$K$$$ ($$$2 \leq N \leq 8$$$, $$$1 \leq K \leq 10^9$$$) — the size of the board and the number of iterations.

The next $$$N$$$ lines contain $$$N$$$ characters each, describing the initial state of the board.

Let $$$S_{i,j}$$$ be the character in the $$$i$$$-th row and $$$j$$$-th column:

$$$\bullet$$$ $$$S_{i,j} = \texttt{'1'}$$$ if the cell is alive,

$$$\bullet$$$ $$$S_{i,j} = \texttt{'0'}$$$ if the cell is dead,

$$$\bullet$$$ $$$S_{i,j} = \texttt{'#'}$$$ if the cell is uninhabitable.

Output

Print $$$N$$$ lines, each containing $$$N$$$ characters, representing the final state of the board after $$$K$$$ iterations.

Examples
Input
4 1
#101
0000
1100
1100
Output
#101
1111
0000
0000
Input
2 1000000000
01
##
Output
00
##