Problem D
Welcome Sign

Amanda is opening a new bakery in town. She will put up a fancy LED sign to show a grand opening message on the storefront window. The sign has $r$ rows and $c$ columns of display units. Each unit can display one letter or be blank.

Amanda has written a message consisting of exactly $r$ words. She will arrange them onto the LED sign such that each row will display one word from the message in order. Each word must be as centered as possible, which means that if the number of blanks on the left side and right side of the word are $l$ and $r$, then $|l - r|$ must be as close to zero as possible. On those rows where $l$ cannot equal $r$, Amanda would like to balance the number of blanks on the two sides. More specifically, for the first and every other such row ($1^{\texttt{st}}$, $3^{\texttt{rd}}$, $5^{\texttt{th}}$, and so forth), she would like $l$ to be less than $r$. For the other rows ($2^{\texttt{nd}}$, $4^{\texttt{th}}$, $6^{\texttt{th}}$, and so forth), she would like $l$ to be greater than $r$.

What would the sign look like after Amanda sets it up according to the above?

Input

The first line of input contains two integers $r$ and $c$ ($1\leq r, c \leq 50$), the number of rows and the number of columns of display units.

The next $r$ lines each contain a word with at least one and at most $c$ lowercase letters (a–z), giving the words to display per row in order.

Output

Output $r$ lines. Each line must contain exactly $c$ characters representing the displayed characters on one row of the LED sign. Output a dot (.) for each blank display unit.

8 7
welcome
we
are
open
free
coffee
for
icpc

welcome
..we...
..are..
..open.
.free..
.coffee
..for..
.icpc..