- Time limit: 1.00 s
- Memory limit: 512 MB
- $h$: the number of lines in a page
- $w$: the number of characters in a line
- $p$: the indentation width (the number of spaces)
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$
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.