“分院帽”的工作确实很轻松；工作影响力大，拥有绝对的权威，而且每年有 364 天的假期。然而，这顶帽子决定它还可以做得更好——它非常想成为一名终身教授。

最近，这顶帽子在充足的闲暇时间里阅读了计算机科学论文。当然，作为一顶分院帽，它对学习更多关于排序算法的知识特别感兴趣。

这顶帽子的新贡献是一类被称为“有损排序算法”的算法。这些算法通常通过移除部分输入元素来使输入更容易排序（例如 Dropsort 算法），而不是对所有输入进行排序。

这顶帽子打算更进一步——它要发明一种针对数字的有损排序算法，该算法不会移除任何输入的数字，甚至会保持它们在原位，而是通过改变数字中的某些位来使列表变得有序。

排序操作的损耗程度取决于改变了多少位数字。为了确保列表有序，最少需要改变多少位数字？

分院帽。图片由 Lisa Abose 提供

输入格式

输入包含： 一行包含整数 $n$ 和 $m$ ($1 \le n \le 40, 1 \le m \le 400$)，分别表示数字的个数和每个数字的位数。 $n$ 行，每行包含一个整数 $v$ ($0 \le v < 10^m$)。这些数字均已补零至恰好 $m$ 位。

输出格式

输出数组的排序版本，要求在使数字有序的前提下，改变的数字位数最少（数字必须保持补零至 $m$ 位）。如果存在多个最优解，你可以给出其中任意一个。

样例

样例输入 1

5 3
111
001
000
111
000

样例输出 1

001
001
001
111
200

样例输入 2

15 3
999
888
777
666
555
444
333
222
111
222
333
444
555
666
999

样例输出 2

199
288
377
466
555
644
733
822
911
922
933
944
955
966
999