Имея много свободного времени, коровы Фермера Джона часто играют в видеоигры.
Одна из их любимых игр похожа на Puyo Puyo. Коровья версия этой игры называется
Му-Му.
Игра Му-Му происходит на высокой узкой решётке из \(N\) ячеек в высоту и
(\(1 \leq N \leq 100\)) и 10 ячеек в ширину.
Вот пример для \(N = 6\):
0000000000
0000000300
0054000300
1054502230
2211122220
1111111223
Каждая ячейка или пустая (обозначена 0) или содержит стог сена одного из 9
различных цветов (обозначенных символами 1..9). Гравитация вынуждает стоги сена
падать вниз, поэтому никогда 0 не будет ниже, чем стог сена.
Две ячейки принадлежат одному и тому же связному региону, если они имеют общую
вертикальную или горизонтальную сторону и один и тот же цвет, отличный от 0.
Каждый раз, когда регион начинает содержать \(K\) или более ячеек, все его стоги сена
исчезают - превращаются в 0. Если в один момент времени существует несколько таких
регионов они исчезают все одновременно. Затем, гравитация может вынудить стоги сена
заполнить некоторые из ячеек, которые стали нулевыми. В получившейся конфигурации
могут снова образоваться региона размера не менее \(K\) ячеек. В этом случае они
также исчезают (одновременно, если есть несколько таких регионов). Затем гравитация
вновь двигает вниз стоги сена и процесс повторяется, пока есть хоть один регион,
в котором не менее \(K\) стогов.
По заданной конфигурации доски для Му-Му вычислите финальную картинку
доски после выполнения всех операций.
ФОРМАТ ВВОДА (файл mooyomooyo.in):
Первая строка ввода содержит \(N\) и \(K\) (\(1 \leq K \leq 10N\)).
Оставшиеся \(N\) строк задают начальное состояние доски.
ФОРМАТ ВЫВОДА (файл mooyomooyo.out):
Выведите \(N\) строк, описывающих финальное состояние поля.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 3
0000000000
0000000300
0054000300
1054502230
2211122220
1111111223
|
0000000000
0000000000
0000000000
0000000000
1054000000
2254500000
|