题目描述

小明最近在用软件写文档时发现，在英文内容的键入时，软件会自动添加一些额外的空格到内容中，使得整段英文在文本区域的两端对齐，并且不会出现单个单词被拆分到两行的情况，看上去整齐又美观。

现在给定一篇文章中的 n 个单词，请试着将其按顺序以“两端对齐”的方式输出，要求：

• 单词间至少由一个空格隔开，行末单词后无空格
• 各行字符数均为 m 个，必要时可以在单词间补充额外的空格
• 一行内单词间的空格数要尽量相同，若始终不能均匀分配，那么左侧的空格数可以多一些
• 输出行数要尽可能少一些，也即每行放置的单词要尽可能多一些
• 最后一行要左对齐，单词间不再插入额外的空格，末尾补空格至 m 个字符

输入输出格式

输入格式：

• 第一行输入两个数 n、m
• 接下来 n 行，每行1个单词 $s_i$，均由小写字母构成

输出格式：

• 输出排版后的文章（数据保证有解）

输入输出样例

输入样例：

10 14
to
be
or
not
to
be
that
is
a
question

输出样例：

to  be  or not
to  be that is
a question

样例说明：

第1行在前两个单词后分别额外添加了一个空格； 第2行在第一个单词后额外添加了一个空格； 最后一行在末尾额外添加了 4个空格。 各行均为14个字符，输出的换行符不算入m。

测试点

10个测试点，每个测试点得10分。

每个测试点时间限制1s，内存限制128MB。

数据范围：

• 对于30%的数据：$1<=n<=10^2$
• 对于60%的数据：$1<=n<=10^3$
• 对于100%的数据：$1<=n<=10^4、1<=m<=10^6、1<=∣si∣<=100$