描述

写电子邮件很有趣，然而，遗憾的是，它们看起来并不是非常美观，主要原因是并非所有行的长度都相同。在这个问题中，你的任务是编写一个电子邮件格式化程序，对电子邮件的一个段落进行重新格式化（例如，通过插入空格），使得之后所有行的长度都相同（甚至每个段落的最后一行也是如此）。

执行此任务最简单的方法是在太短的行中的单词之间插入更多的空格。但这并不是最好的方法。考虑以下示例：

****************************
This is the example you are
actually considering.

假设我们希望得到与星号行一样长的行。那么，通过简单地插入空格，我们会得到：

****************************
This is the example you  are
actually        considering.

但是，由于第二行中有很大的间隔，这看起来相当奇怪。通过将单词 “are” 从第一行移到第二行，我们会得到一个更好的结果：

****************************
This  is  the  example   you
are  actually   considering.

当然，这必须进行形式化。为此，我们为单词之间的每个间隔分配一个“不良度”。分配给有 (n) 个空格的间隔的不良度为 ((n - 1)^2)。该程序的目标是最小化所有不良度的总和。例如，第一个示例的不良度是 (1 + 7^2 = 50)，而第二个示例的不良度仅为 (1 + 1 + 1 + 4 + 1 + 4 = 12)。

在输出中，每一行都必须以一个单词开始和结束。（即，在行的开头或结尾不能有间隔。）唯一的例外情况如下：

如果一行只包含一个单词，那么这个单词应放在行的开头，如果该行比应有的长度短，则为该行分配 500 的不良度。（当然，在这种情况下，该行的长度就是这个单词的长度。）

输入

输入包含由几个段落组成的文本。每个段落前面都有一行，该行包含一个整数 (n)，即该段落所需的宽度（(1 \leq n \leq 80)）。

段落由一行或多行组成，每行包含一个或多个单词。单词由 ASCII 码在 $33$ 到 $126$ 之间（包括 $33$ 和 $126$）的字符组成，并且由空格（可能不止一个）分隔。没有单词会比该段落所需的宽度长。一个段落中所有单词的总长度不会超过 $10000$ 个字符。

每个段落都恰好由一个空行终止。输入文件中的段落数量没有限制。

输入文件将由一个以 (n = 0) 开始的段落描述终止。这个段落不应被处理。

输出

输出相同的文本，按照上述方式进行格式化（分别处理每个段落）。

如果有几种方法可以以相同的不良度格式化一个段落，请使用以下算法来选择要输出的方法：设 (A) 和 (B) 是两个解决方案。找到在 (A) 和 (B) 中长度不同的第一个间隔。不要输出这个间隔更大的那个解决方案。

在每个段落之后输出一个空行。

输入示例

28
This is the example you are
actually considering.

25
Writing e-mails is fun, and with this program,
they even look nice.

0

输出示例

This  is  the  example   you
are  actually   considering.

Writing e-mails  is  fun,
and  with  this  program,
they  even   look   nice.

来源

1999 年中欧地区竞赛