Optimal Poem Formatting

Little G is an accomplished poet who enjoys writing poems, but he has always been troubled with the layout issues of his poems. A poem is composed of several sentences. Consecutive short sentences can be put together on the same line separated by a single space (there is no limit on the number of sentences per line). For each poem, Little G defines a standard line length (the total number of characters in that line, including spaces) and wants the actual line lengths to be as close to this standard as possible.

When formatting the poem, the following conditions must be met:

• The original order of the sentences must be preserved.
• No sentence may be split across lines.

In addition, Little G defines a discrepancy for each line as the P^th power of the absolute difference between the actual line length and the standard line length. The total discrepancy of a formatted poem is the sum of the discrepancies of all lines.

Your task is to determine a way to format the given poem so that the total discrepancy is minimized, and then output the formatted poem.

Note: If there are multiple optimal solutions, output any one of them.

inputFormat

The input starts with a line containing two integers L and P, where L is the standard line length and P is the exponent used in the discrepancy calculation.

The second line contains an integer N, the number of sentences in the poem.

Each of the following N lines contains one sentence (without spaces at either end). When a line is formed during formatting, sentences are concatenated with a single space between adjacent sentences.

outputFormat

Output the formatted poem, printing each line on a new line. The formatting should minimize the sum of the discrepancies computed as |(actual line length - L)|^P for each line.

sample

20 2
5
I
am
a
great
poet.

I am a great poet.