Next: Web Reliable Up: No Title Previous: Web Browser Window Placement

Formatting HTML Text

One of the things that a web browser needs to do is to display text in a nicely formatted manner. For this problem, you are to write text formatting program. Your program will input a paragraph of text. This text will consist of a series of words separated by spaces and/or newlines (you may assume that there are no tab characters). A word may contain punctuation characters. The text is terminated by special word ``$$$'', which appears alone on the last line. For example consider the text:

    The quick brown-fox jump$
       over, the   ---                lazy

    dog.
    $$$

The words are ``The'', ``quick-brown'', ``fox'', ``jump$'', ``over,'', ``the'', ``--'', `` lazy'', and ``dog.''. Note that final ``$$$'' is not considered a word.

Your program will also be given an integer indicating the window width w. You are to output the words with a minimum number of spaces between them so that:

(1)

No line has more than w total characters (excluding the newline character).

(2)

For each two words on the same line there is at least one space between them.

(3)

The leftmost character is nonblank and, except for the last line, the rightmost character is nonblank.

(4)

The spaces are to be distributed as evenly as possible between the words. If you cannot generate exactly the same number of spaces between consecutive words, then place the larger number of spaces near the right end of the line. For example (as shown in the line with ``jump$'' below) if you have 4 words and hence 3 gaps between them, and you need a total of 5 spaces to fill up the line, then the spaces should be distributed 1-2-2 in the gaps.

Given a width of 21, the above text would be displayed as follows.

    123456789012345678901          <--- This reference line is not printed
    The  quick  brown-fox
    jump$ over,  the  ---
    lazy dog.

Input format

The first line of the input contains just the input width w. Starting with the next line, the text is given. The last line of the input contains the single word ``$$$''. This word appears nowhere else in the text. As a simplifying assumption you may assume no two consecutive words are so long that they cannot both fit on a single line with a single space between them. You may assume that each word has at most 50 characters, that there are at most 5,000 words total, and that w is at most 100.

Output format

The output consists of the words of text. There should be no leading spaces or trailing spaces.

Example

Input:

21
The quick brown-fox jump$
   over, the   ---                lazy

dog.
$$$

Output:

The  quick  brown-fox
jump$ over,  the  ---
lazy dog.

Input:

30
When in the Course of human events,
it becomes necessary for one people
to dissolve   the political bands
which have connected them with another,
and to   assume among the
powers of the earth, the separate
and equal station   to which
the Laws of Nature and of
Nature's   God entitle them, a decent
respect to the opinions of mankind
requires   that   they should
declare the causes which impel
them to the   separation.
$$$

Output:

When in the  Course  of  human
events, it  becomes  necessary
for one people to dissolve the
political  bands  which   have
connected them  with  another,
and to assume among the powers
of the earth, the separate and
equal  station  to  which  the
Laws of Nature and of Nature's
God  entitle  them,  a  decent
respect  to  the  opinions  of
mankind  requires  that   they
should  declare   the   causes
which  impel   them   to   the
separation.

Test data used in judging

Input 1	Output 1
Input 2	Output 2
Input 3	Output 3
Input 4	Output 4
Input 5	Output 5
Input 6	Output 6
Input 7	Output 7
Input 8	Output 8
Input 9	Output 9

Our Solution

Next: Web Reliable Up: No Title Previous: Web Browser Window Placement