Life on a Ring

Time Limit: 1 Second    Memory Limit: 32768 KB

The Game of Life is not your typical computer game. It is a 'cellular automaton', and was invented by Cambridge mathematician John Conway.

This game became widely known when it was mentioned in an article published by Scientific American in 1970. It consists of a collection of cells which, based on a few mathematical rules, can live, die or multiply. Depending on the initial conditions, the cells form various patterns throughout the course of the game.

Now, let's define a similar but much easier version of The Game of Life. All the cells lie on a ring, each cell has four neighboring positions: those at distance one or two from it on each side. The rules are similar to those of two-dimensional Life except (1) a dead cell with either two or three living neighbors will become alive in the next generation, and (2) a living cell dies if it has zero, one, or three living neighbors. (Hence a dead cell with zero, one, or four living neighbors stays dead; a living cell with two or four living neighbors stays alive.)

Given an initial condition of the cells, you're to find the layout of the selected generation.

Input

Each case begin with a line with two positive integers N (5 <= N <= 20) and T, the size of the ring and the generation you're to find. The second line contains N integers (0 and 1), indicating a dead cell and a living cell.

Input cases are separated with a blank line. Proceed to the end of file.

Output

For each case, print the layout in a line, same as input. There is one space between numbers.

Sample Input

5 1
0 1 0 1 0

7 2
0 1 0 1 1 1 0

Sample Output

1 0 1 0 1
0 1 1 1 0 0 0

Submit

Source: ZOJ Monthly, June 2003