Му-Му
Имея много свободного времени, коровы Фермера Джона часто играют в видеоигры. Одна из их любимых игр похожа на Puyo Puyo. Коровья версия этой игры называется Му-Му.
Игра Му-Му происходит на высокой узкой решётке из n ячеек в высоту и 10 ячеек в ширину. Вот пример для n = 6:
0000000000 0000000300 0054000300 1054502230 2211122220 1111111223
Каждая ячейка или пустая (обозначена 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. После того, как они одновременно исчезнут, доска примет вид:
0000000000 0000000300 0054000300 1054500030 2200000000 0000000003
Затем, вследствие действия гравитации, доска примет вид:
0000000000 0000000000 0000000000 0000000000 1054000300 2254500333
Опять имеется регион размера не менее k (цветом 3). После его удаления, получаем финальную конфигурацию:
0000000000 0000000000 0000000000 0000000000 1054000000 2254500000