Formatting Text

Writing e-mails is fun, but unfortunately they often do not look very neat, mainly because the lines are not all the same length. In this problem your task is to write an e-mail formatting program that reformats a paragraph (by inserting spaces) so that afterwards every line has the same length — including the last line of each paragraph.

The simplest way would be to insert extra spaces between the words of any line that is too short. But this is not always the best approach. Consider the following example:

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

Suppose we want every line to be as long as the row of stars. Simply inserting spaces would give:

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

This looks rather odd because of the large gap in the second line. By moving the word "are" from the first line to the second, we get a better result:

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

To formalize this, we assign a badness to every gap between two words. A gap of $n$ spaces has a badness of $(n-1)^2$. The goal of the program is to minimize the sum of all badnesses. For example, the badness of the first layout is $1 + 7^2 = 50$, whereas the badness of the second one is only $1 + 1 + 1 + 4 + 1 + 4 = 12$.

In the output, every line must begin and end with a word (i.e. there can be no gap at the beginning or the end of a line). The only exception is the following:

• If a line contains only one word, that word is placed at the beginning of the line, and a badness of $500$ is assigned to this line if it is shorter than it should be. (In this case the length of the line is simply the length of the word.)

The input consists of several paragraphs. Each paragraph is preceded by a line containing a single integer $n$, the desired width of the paragraph ($1 \le n \le 80$).

A paragraph consists of one or more lines, each containing one or more words. Words are made of characters with ASCII codes from 33 to 126 inclusive and are separated by one or more spaces. No word is longer than the desired width of its paragraph. The total length of all words in a single paragraph does not exceed 10000 characters.

Each paragraph is terminated by exactly one blank line. There is no limit on the number of paragraphs.

The input ends with a paragraph description whose width is $n = 0$; this paragraph must not be processed.

For each paragraph, output the same text reformatted as described above (each paragraph is processed independently). Every line of a formatted paragraph has the same width $n$, except that a line containing a single word may be shorter.

If a paragraph can be formatted in several ways with the same minimum total badness, choose which one to output as follows. Let $A$ and $B$ be two such layouts. Looking at the gaps between words in reading order, find the first gap whose width differs between $A$ and $B$; do not output the layout in which that gap is bigger. (Equivalently, among all minimum-badness layouts, output the one whose sequence of gap widths is lexicographically smallest.)

Print a blank line between consecutive paragraphs.