由于手上(更确实的,蹄子上)有大把的空余时间,Farmer John 的农场里的奶牛经常玩电子游戏消磨时光。
她们最爱的游戏之一是基于一款人类中流行的电子游戏噗呦噗呦的奶牛版;名称当然叫做哞呦哞呦。
哞呦哞呦是在一块细长的棋盘上进行的游戏,高 N 格,宽 10 格。
这是一个 N=6的棋盘的例子:
0000000000 0000000300 0054000300 1054502230 2211122220 1111111223
每个格子中或者是空的(用 0 表示),或者是九种颜色之一的干草捆(用字符 1..9 表示)。
重力会使得干草捆下落,所以没有干草捆的下方是 0。
如果两个格子水平或垂直方向直接相邻,并且为同一种非 0 颜色,那么这两个格子就属于同一个连通区域。
任意时刻出现至少 K 个格子构成的连通区域,其中的干草捆就会全部消失,变为 0。
如果同时出现多个这样的连通区域,它们同时消失。
随后,重力可能会导致干草捆向下落入某个变为 0 的格子。
由此形成的新的布局中,又可能出现至少 K 个格子构成的连通区域。
若如此,它们同样也会消失(如果又有多个这样的区域,则同时消失),然后重力又会使得剩下的方块下落,这一过程持续进行,直到不存在大小至少为 K 的连通区域为止。
给定一块哞呦哞呦棋盘的状态,输出这些过程发生之后最终的棋盘的图案。
输入的第一行包含 N 和 K。 以下 N 行给出了棋盘的初始状态。
输出 N 行,描述最终的棋盘状态。 数据范围 1≤N≤100, 1≤K≤10N
6 3
0000000000
0000000300
0054000300
1054502230
2211122220
1111111223
0000000000
0000000000
0000000000
0000000000
1054000000
2254500000