Word wrapping P59168

Word wrapping is breaking a text into lines so that they fit into the width w of a page. For simplicity, suppose that the text has only n words [t₀, …, t_n−1] without punctuation marks. If we decide to include the words [t_i, …, t_j] separated with spaces in the k-th line, and the sum of lengths of those words is ℓ, then we will use ℓ + j − i characters. Hence, we will have exactly s_k = w − ℓ − j + i unused spaces at the end of the k-th line.

Let us fix an integer constant c ≥ 1. We can define the uglyness of each line k as u_k = (s_k)^c. A way of choosing where to break the lines is to minimize the resulting ∑_k u_k, where the sum is over the indices k of all lines except the last one (we do not care if it has unused space).

Given a text, can you wrap it according to this method?

Input

Input consists of several cases, each one with w, c and n, followed by n words made up of between 1 and w lowercase letters. You can assume 1 ≤ w ≤ 80, 1 ≤ c ≤ 2, and 1 ≤ n ≤ 10⁴.

Output

For every case, print the result of wrapping the text according to the method above. If there are several solutions with minimum total uglyness, choose the one that maximizes the number of words of the first line; in case of a tie, maximize the number of words of the second line, and so on. Print a line with w dashes at the end of each case.