Whitespace King: Aligning Columns

Interview

Time limit1sMemory limit128 MB

Summary

Reformat text lines so that words in each column line up to a width equal to the longest word in that column, with single spaces separating columns.

Level: Easy3 of 10
Topics: String, Implementation, Array
Solved: No attempts yet

Problem

Just as food that looks good tastes good, neatly organized text is easier to read than text thrown together carelessly. In this problem you split the given text into words and print it prettily, with every column lined up.

Here, a piece of text is pretty when, across every line of the text, the i-th word starts at the same position (column). For example, consider the text below.

a bc z
de f zz

The second words, bc and f, start at different positions, so this text is not pretty. If we insert spaces appropriately to line up their starting positions, we get:

a  bc z
de f  zz

Now the first words a and de both start at column 0, the second words bc and f both start at column 3, and the third words z and zz both start at column 6, so the text is pretty.

Given a piece of text, insert and remove spaces as needed to make it pretty, and print the result. The text contains only spaces, line breaks, and characters with ASCII values from 33 to 126.

Input

The text is given over several lines. Words are separated by spaces, and each word is at most 80 characters long. Each line contains at most 180 characters (including spaces), and the text may contain up to 1000 lines.

Output

Print the given text aligned prettily. The width of each column is the length of the longest word appearing in that column, and adjacent columns are separated by a single space. On each line print no unnecessary spaces beyond those needed to separate words: no leading or trailing spaces, and no spaces after the last word on a line. The resulting alignment is uniquely determined.

Examples3

Example 1

Input

  start:  integer;    // begins here
stop: integer; //  ends here  
 s:  string;   
c:   char; // temp

Expected output

start: integer; // begins here
stop:  integer; // ends   here
s:     string;
c:     char;    // temp

Example 2
Input
```
a bc z
de f zz
```
Expected output
```
a  bc z
de f  zz
```

Example 3

Input

   foo    bar   
  baz qux

Expected output

foo bar
baz qux