在基于 Unix 的操作系统中，最常用的命令之一是 ls，它以字典序显示目录中的所有文件名。最基本的形式是 ls 将每个文件名打印在单独的一行上，但为了提高可读性并节省屏幕空间，列表通常被拆分为多列并排显示。

你的朋友正在编写一本关于 NWERC 的书，并让你负责编辑每一章末尾的相关术语表。每个术语表都必须使用与 ls 相同的多列布局，因此你决定采取偷懒的办法：为术语表中的每个单词创建一个同名的空文件，然后直接让 ls 完成繁重的工作。

不幸的是，你的朋友对你的布局并不满意，并抱怨其中一些布局占用了太多的垂直空间。你这种方法的问题在于，ls 总是形成等高的列（最后一列除外，它可能较短）。如果能更自由地选择列高，有时可以减少所需的行数：

图 G.1：通过可变列高节省两行。

你勉强决定编写自己改进版的 ls，即 ls--，它同样以字典序显示目录内容，但使用可变列高，以始终实现尽可能少的行数。

列具有固定的宽度，即该列中最长文件名的长度，并且各列之间由单个空格分隔。每一列中的名称必须左对齐，并使用空格填充至列宽。此外，你使用的终端具有固定的宽度 $w$ 个字符，表格不得超过此宽度。

给定目录内容作为文件名列表，找到一种最优的列布局，使打印整个列表所需的行数最小。

输入格式

输入包含： 一行，包含两个整数 $n$ 和 $w$ ($1 \le n, w \le 5\,000$)，表示文件数量和终端宽度。 $n$ 行，每行包含一个文件名 $s$ ($1 \le |s| \le w$，$s$ 由小写英文字母组成)。文件名各不相同且按字典序排列。字母总数最多为 $10^6$。

输出格式

输出一种列出给定文件名的最优方式： 一行，包含两个整数 $r$ 和 $c$，表示使用的行数和列数。 一行，包含 $c$ 个正整数 $a_1, a_2, \dots, a_c$，表示各列的宽度。 文件名表格，需遵循以下格式： 共有 $c$ 列，其中第 $i$ 列的宽度为 $a_i$。在每一列中，最多有 $r$ 个文件名，它们左对齐并排列在顶部。 文件名使用空格对齐，列与列之间恰好有一个空格。 表格的总宽度最多为 $w$。 * 按列读取时，文件名按字典序排列。

注意，与其他问题不同，你必须严格遵守上述关于空白字符的格式规则。但是，我们仍然允许每行末尾存在尾随空格，即使这些空格超过了宽度 $w$。

样例

样例输入 1

9 30
algorithm
contest
eindhoven
icpc
nwerc
programming
regional
reykjavik
ru

样例输出 1

3 4
9 5 11 2
algorithm icpc programming ru
contest nwerc regional
eindhoven reykjavik

样例输入 2

6 10
aaa
bb
ccccc
ddd
eeeee
fffff

样例输出 2

4 2
3 5
aaa ccccc
bb ddd
eeeee
fffff

样例输入 3

5 15
pppp
ppppp
pq
pqab
xyzff

样例输出 3

2 3
5 2 5
pppp pq pqab
ppppp xyzff