Với rất nhiều thời gian rảnh trong tay (hay đúng hơn là trong móng), những cô bò ở trang trại của Nông dân John thường giết thời gian bằng cách chơi trò chơi điện tử. Một trong những trò yêu thích của chúng dựa trên trò chơi nổi tiếng của con người có tên Puyo Puyo; phiên bản dành cho bò tất nhiên được gọi là Mooyo Mooyo.

Mooyo Mooyo được chơi trên một lưới cao và hẹp gồm \(N\) ô theo chiều cao (\(1 \leq N \leq 100\)) và 10 ô theo chiều rộng. Dưới đây là một ví dụ với \(N = 6\):

0000000000
0000000300
0054000300
1054502230
2211122220
1111111223

Mỗi ô hoặc trống (được biểu diễn bằng 0), hoặc chứa một kiện cỏ khô thuộc một trong chín màu khác nhau (được biểu diễn bằng các ký tự 1..9). Trọng lực khiến các kiện cỏ khô rơi xuống, vì vậy không bao giờ có một ô 0 nằm bên dưới một kiện cỏ khô.

Hai ô thuộc cùng một vùng liên thông nếu chúng kề cạnh trực tiếp theo chiều ngang hoặc chiều dọc và có cùng một màu khác 0. Bất cứ khi nào tồn tại một vùng liên thông có ít nhất \(K\) ô, tất cả các kiện cỏ khô trong vùng đó biến mất và các ô của chúng trở thành 0. Nếu cùng lúc có nhiều vùng liên thông như vậy, tất cả chúng biến mất đồng thời. Sau đó, trọng lực có thể khiến các kiện cỏ khô rơi xuống để lấp một số ô vừa trở thành 0. Trong cấu hình mới, có thể lại xuất hiện các vùng liên thông có kích thước ít nhất \(K\). Nếu có, chúng cũng biến mất (đồng thời nếu có nhiều vùng như vậy), rồi trọng lực kéo các ô còn lại xuống, và quá trình lặp lại cho đến khi không còn vùng liên thông nào có kích thước ít nhất \(K\).

Cho trạng thái của một bàn Mooyo Mooyo, hãy in ra hình ảnh cuối cùng của bàn sau khi các thao tác trên hoàn tất.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(K\) (\(1 \leq K \leq 10N\)). \(N\) dòng còn lại mô tả trạng thái ban đầu của bàn.

Dữ liệu ra

In ra \(N\) dòng mô tả trạng thái cuối cùng của bàn.

Ví dụ

6 3
0000000000
0000000300
0054000300
1054502230
2211122220
1111111223

0000000000
0000000000
0000000000
0000000000
1054000000
2254500000

0000000000
0000000300
0054000300
1054500030
2200000000
0000000003

0000000000
0000000000
0000000000
0000000000
1054000300
2254500333

0000000000
0000000000
0000000000
0000000000
1054000000
2254500000

Nguồn

Đề bài gốc: USACO 2018 December Contest, Silver — Mooyo Mooyo

Tác giả: Brian Dean