LJUST

Nili company wants to develop a simple text editor. Mohammad, a member of the development team, has been assigned an essential feature: justify line. You have used word processing software and its justify line feature before. Help him write a program that reads lines as input and prints them justified.

Keep the following in mind while writing the program:

• Each line is a paragraph.
• To justify a line, pad it by adding extra white spaces between words from left to right. Keep the white spaces balanced between words. Do not add all white spaces after the first word.
• Only justify a line if the number of characters in it is >= floor(C/2).
• Lines longer than C must be wrapped to the next line.
• No justified line may start or end with whitespace.
• Do not remove blank lines. A blank line is a line that has no non-blank character in it.

The first line contains the maximum number of characters per line, C (C >= 50).

The next N lines (N < 100000) each contain W words (W < 10000).

Input ends with the line ENDOFINPUT. That line is not part of the input.

Note: no word is longer than C.

Print the lines justified.

A line must contain only 50 characters. So:

• The first line could not be longer than those five words (49 characters including spaces), and only one space was needed to justify it, added after the first leftmost word.
• The second line was 32 characters long, which is >= floor(50 / 2), so 19 more spaces were added to justify it.
• The third line was justified, and the extra words ("among the") were wrapped into the next line, which cannot be justified.