Му-Му - Задачи

Имея много свободного времени, коровы Фермера Джона часто играют в видеоигры. Одна из их любимых игр похожа на Puyo Puyo. Коровья версия этой игры называется Му-Му.

Игра Му-Му происходит на высокой узкой решётке из n ячеек в высоту и 10 ячеек в ширину. Вот пример для n = 6:

Каждая ячейка или пустая (обозначена 0) или содержит стог сена одного из 9 различных цветов (обозначенных символами 1..9). Гравитация вынуждает стоги сена падать вниз, поэтому никогда 0 не будет ниже, чем стог сена.

Две ячейки принадлежат одному и тому же связному региону, если они имеют общую вертикальную или горизонтальную сторону и один и тот же цвет, отличный от 0. Каждый раз, когда регион начинает содержать k или более ячеек, все его стоги сена исчезают - превращаются в 0. Если в один момент времени существует несколько таких регионов они исчезают все одновременно. Затем, гравитация может вынудить стоги сена заполнить некоторые из ячеек, которые стали нулевыми. В получившейся конфигурации могут снова образоваться региона размера не менее k ячеек. В этом случае они также исчезают (одновременно, если есть несколько таких регионов). Затем гравитация вновь двигает вниз стоги сена и процесс повторяется, пока есть хоть один регион, в котором не менее k стогов.

По заданной конфигурации доски для Му-Му вычислите финальную картинку доски после выполнения всех операций.

Входные данные

Первая строка ввода содержит n (1 ≤ n ≤ 100) и k (1 ≤ k ≤ 10n). Оставшиеся n строк задают начальное состояние доски.

Выходные данные

Выведите n строк, описывающих финальное состояние поля.

Пример

В примере если k = 3, имеется связный регион размера не менее k цвета 1 и цвета 2. После того, как они одновременно исчезнут, доска примет вид:

Затем, вследствие действия гравитации, доска примет вид:

Опять имеется регион размера не менее k (цветом 3). После его удаления, получаем финальную конфигурацию:

Лимит времени 1 секунда

Лимит использования памяти 128 MiB

Входные данные #1

Выходные данные #1

Источник 2018 USACO Декабрь, Серебро