Mooyo Mooyo#10398

Mooyo Mooyo

1 second

128 megabytes

Easy

With plenty of free time on their hands (or rather, hooves), the cows on Farmer John's farm often pass the time by playing video games. One of their favorites is based on a popular human video game called Puyo Puyo; the cow version is, of course, called Mooyo Mooyo.

Mooyo Mooyo is played on a tall, narrow grid that is $n$ cells tall and $10$ cells wide. Here is an example with $n = 6$ n = 6:

Each cell is either empty (denoted by $0$ ) or contains a haybale of one of nine colors (denoted by the digits $1$ to $9$ ). Gravity makes haybales fall downward, so there is never an empty cell below a haybale.

Two cells belong to the same connected region if they are adjacent horizontally or vertically and have the same nonzero color. Whenever a connected region of at least $k$ cells exists, all of its haybales disappear and the cells become empty. If several such regions exist at the same time, they all disappear simultaneously. After that, gravity may cause haybales to fall down into some of the newly emptied cells. The resulting configuration may again contain connected regions of at least $k$ cells. If so, they also disappear (simultaneously, if there are several), gravity again pulls the remaining haybales down, and the process repeats until no connected region of at least $k$ cells remains.

Given the initial state of a Mooyo Mooyo board, print the final state of the board after all these operations.

Input

The first line contains two integers $n$ and $k (1 \leq n \leq 100, 1 \leq k \leq 10 n)$ k~(1 \le n \le 100, 1 \le k \le 10n). Each of the next $n$ lines contains $10$ digits and describes one row of the initial board.

Output

Print $n$ lines describing the final state of the board in the same format.

Examples

In the example above, if $k = 3$ k = 3, there is a connected region of at least $k$ cells of color $1$ and another one of color $2$ . After they are removed simultaneously, the board temporarily looks like this:

Then gravity takes effect, and the haybales fall into the following configuration:

Again, there is a region of at least $k$ cells (of color $3$ ). Removing it yields the final configuration of the board:

Example 1