Text Justification

Text editing or rather preparing it to publishing - was among the first uses for computers besides military and scientific calculations. One of the popular tasks in this field was text alignment - there are several ways of aligning text (left, centered etc) - of them most popular for books is justified - when both left and right borders of text form a straight line, though some additional spacing could be added between the words in the middle.

In the days when text was printed with "monotype" fonts (e.g. on alfanumeric displays) spaces could only have integer width (e.g. there could be one, or two, or three etc spaces between words). Nowadays with mostly graphical interfaces fractional spacing is also possible. But we shall work with older, integer-spacing style.

In this problem we get a single paragraph of some text. It is randomly split to lines for convenience, but please merge them and regard as single line as a first step.

Besides the text we are given the wanted width of the text.

The goal is to re-split text to lines and add some spaces where necessary, to conform to the following rules:

1. Every line should have length matching requested text width, with no spaces at start or end.
2. Every line should contain as many of the following words as possible.
3. Spaces inside the line could not have width differing by more than 1.
4. Last line ("dangling") should not be justified (use single spaces in it).

(punctuations belong to words unless not separated from them on both sides,)

You are free about variations of spacing as long as result conforms to the third rule: e.g. where to insert longer spaces and where shorter - this is up to your taste.

Really justification rules could be more complicated - this is famous Knuth's problem of making justified text "more elegant" by reducing vertical "channels" of spaces etc - but we do not dive in such depths for now!

Input data: the first line gives wanted width of text. Then the text follows in several lines.

Answer - the text, justified according to the rules given above.

Example:

input:

23
Four score and seven years ago
our fathers brought forth,
upon this continent, a new nation, conceived in
liberty and dedicated to the proposition
that all men are created equal.

answer:

Four  score  and  seven
years  ago our  fathers
brought   forth,   upon
this  continent,  a new
nation,   conceived  in
liberty  and  dedicated
to the proposition that
all  men  are   created
equal.