Insert Whitespace

• Time limit: 1.00 s
• Memory limit: 512 MB

In this problem, your task is to typeset a given text that consists of $n$ paragraphs. You are given three parameters:

• $h$: the number of lines in a page
  
• $w$: the number of characters in a line
  
• $p$: the indentation width (the number of spaces)
  

All pages except the last page must have exactly $h$ lines, and in each paragraph all lines except the last line must have exactly $w$ characters. Paragraphs must be fully justified, and there must always be 1 or 2 spaces between two words.

In addition, you cannot have orphan or widow lines, that is, if there is a page break in the middle of a paragraph, there have to be at least 2 lines of paragraph before the page break and at least 2 lines of paragraph after the page break.

Input

The first input line has four integers $n$, $h$, $w$ and $p$.

After this, there are $n$ lines, each of which contains a paragraph. Each paragraph consists of words that are separated by spaces. Each word consists of English letters, numbers and punctuation marks.

Output

Print a valid way to typeset the text. Use the character # to indicate page breaks. If there are no solutions, only print "IMPOSSIBLE".

Note: Make sure that your output does not have extra whitespace.

Constraints

• $2 \le h \le 50$
  
• $1 \le p < w \le 80$
  
• each word has at most $w$ characters
  
• the total number of words is at most $5000$
  

Example

Input:
2 6 33 5
Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua.
Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat.

Output:
     Lorem  ipsum dolor sit amet,
consectetur  adipiscing elit, sed
do  eiusmod  tempor incididunt ut
labore et dolore magna aliqua.
     Ut  enim  ad  minim  veniam,
quis nostrud exercitation ullamco
#
laboris  nisi  ut  aliquip  ex ea
commodo consequat.