Mooyo Mooyo#10398

Mooyo Mooyo

1 секунда

128 мегабайтів

Легка

Маючи багато вільного часу (а точніше, вільних копит), корови на фермі Фермера Джона часто бавлять час, граючи у відеоігри. Одна з їхніх улюблених ігор заснована на популярній людській відеогрі під назвою Puyo Puyo; коров'яча версія, звісно, називається Mooyo Mooyo.

Mooyo Mooyo грається на високому, вузькому полі, яке має $n$ клітинок у висоту та $10$ клітинок у ширину. Ось приклад з $n = 6$ n = 6:

Кожна клітинка або порожня (позначається $0$ ), або містить тюк сіна одного з дев'яти кольорів (позначається цифрами від $1$ до $9$ ). Гравітація змушує тюки сіна падати вниз, тому під тюком сіна ніколи не буває порожньої клітинки.

Дві клітинки належать до одного зв'язного регіону, якщо вони суміжні по горизонталі чи вертикалі та мають однаковий ненульовий колір. Щоразу, коли існує зв'язний регіон з принаймні $k$ клітинок, усі його тюки сіна зникають, а клітинки стають порожніми. Якщо одночасно існує декілька таких регіонів, вони всі зникають одночасно. Після цього гравітація може призвести до того, що тюки сіна впадуть у деякі з щойно звільнених клітинок. Отримана конфігурація може знову містити зв'язні регіони з принаймні $k$ клітинками. Якщо так, вони також зникають (одночасно, якщо їх декілька), гравітація знову притягує тюки сіна, що залишилися, вниз, і процес повторюється, доки не залишиться жодного зв'язного регіону з принаймні $k$ клітинками.

Маючи початковий стан поля Mooyo Mooyo, виведіть кінцевий стан поля після виконання всіх цих операцій.

Вхідні дані

Перший рядок містить два цілих числа $n$ та $k (1 \leq n \leq 100, 1 \leq k \leq 10 n)$ k~(1 \le n \le 100, 1 \le k \le 10n). Кожен з наступних $n$ рядків містить $10$ цифр та описує один рядок початкового поля.

Вихідні дані

Виведіть $n$ рядків, що описують кінцевий стан поля у тому ж форматі.

Приклади

У прикладі вище, якщо $k = 3$ k = 3, існує зв'язний регіон з принаймні $k$ клітинками кольору $1$ та ще один кольору $2$ . Після того, як їх видалено одночасно, поле тимчасово виглядає так:

Згодом гравітація вступає в дію, і тюки сіна падають, утворюючи таку конфігурацію:

Знову існує регіон з принаймні $k$ клітинками (кольору $3$ ). Видаливши його, отримуємо кінцеву конфігурацію поля:

Приклад 1