A Very Nasty Text Formatter 

Input and Output

This problem deals with pretty-printing of an arbitrary text. You are given a text (see also EBNF below) composed of some paragraphs. Each paragraph is initiated by an integer n. You are expected to output this paragraph in such a way that every row is <CR>-terminated and is except for the last one exactly n characters long (<CR> not counted).

This justified output should be done by inserting some extra spaces between the words of a row. Divide the spaces left as equally as possible among the spaces between words. In case you can't divide them equally, the leftmost spaces between words should be longer than the rightmost ones. In some cases, you may be forced to hyphenate a word to achieve justified output. Do this hyphenation where you want because you do not have to follow any linguistic rules. You should do as few hyphenations as possible. However, if it is impossible to justify a line of the text, output it left-justified. The assumptions that you can make are

1. The text follows the EBNF.
2. 3 < n < 1000.
3. There are no words longer than thousand characters.

Note 1: The text is built following this EBNF

    text = paragraph {paragraph} <eof>.
    paragraph = n " " word {" " word} <CR>.
    n = digit {digit}.
    word = letter {letter} [mark].
    digit = "0" | "1" | "2" | ... | "8" | "9".
    letter = "A" | "B" | ... | "Y" | "Z" | "a" | "b" | ... | "y" | "z".
    mark = "." | "," | ";" | ":".

Note 2: The explicit <CR>'s and <eof>'s have been added on the sample input and output to make it readable. They won't exist on the input and output files.

Sample Input

20 This is an example of a paragraph which is prettyprinted on a row with a
length of twenty.<CR>
15 This is an example of a paragraph which is prettyprinted on a row with a 
length of fifteen.<CR>
10 This is an example of a paragraph which is prettyprinted on a row with a
length of ten.<CR>
5 This is an example of a paragraph which is prettyprinted on a row with a
length of five.<CR>
<eof>

Sample Output

This  is  an example<CR>
of a paragraph which<CR>
is  prettyprinted on<CR>
a  row with a length<CR>
of twenty.<CR>
This    is   an<CR>
example   of  a<CR>
paragraph which<CR>
is prettyprint-<CR>
ed   on  a  row<CR>
with  a  length<CR>
of fifteen.<CR>
This is an<CR>
example of<CR>
a paragra-<CR>
ph   which<CR>
is pretty-<CR>
printed on<CR>
a row with<CR>
a   length<CR>
of ten.<CR>
This<CR>
is an<CR>
exam-<CR>
ple<CR>
of  a<CR>
para-<CR>
graph<CR>
which<CR>
is p-<CR>
rett-<CR>
ypri-<CR>
nted<CR>
on  a<CR>
row<CR>
with<CR>
a le-<CR>
ngth<CR>
of f-<CR>
ive.<CR>
<eof>