P1912 [NOI2009] Poet Little G

Little G is an excellent poet who often writes poems for fun. However, he has always been troubled by typesetting. A poem contains several sentences. Some consecutive short sentences can be put on the same line separated by single spaces. Note that there is no limit on how many sentences can be placed on a line. Little G defines a standard line length for each poem (a line’s length is the total number of symbols in that line). He hopes that, after typesetting, the length of every line is close to the standard line length. Clearly, the original order of sentences must not be changed, and Little G does not allow a sentence to be split across lines. Under these two conditions, he defines the disharmony of a line as the $P$-th power of the absolute difference between the line’s actual length and the standard line length. The disharmony of a typesetting is the sum of the disharmonies of all lines. Little G has recently composed several poems. Please typeset each poem so that the disharmony is minimized, and tell him the result.

The first line of the input contains an integer $T$, the number of poems. Then follow $T$ poems, each being one test case. For each test case, the first line contains three positive integers $N, L, P$ separated by spaces: $N$ is the number of sentences in the poem, $L$ is the standard line length, and $P$ is as defined above. Starting from the next line, there are $N$ lines, each containing one sentence. A sentence consists of symbols such as English letters, digits, and punctuation (ASCII codes from $33$ to $127$, but not including `-`).

For each test case, if the minimal disharmony does not exceed $10^{18}$, print that disharmony on the first line. Then print the typeset poem on the following lines. Note: between two adjacent sentences on the same line, insert exactly one space. If there are multiple optimal solutions (i.e., with the same minimal disharmony), you may output any of them. If the minimal disharmony exceeds $10^{18}$, output `Too hard to arrange`. After each test case, output a line `--------------------` consisting of exactly 20 `-` characters (ASCII code $45$). Do not print extra blank lines or spaces.

#### Explanation for Sample Input and Output 1 In the first two test cases, the actual length of each line is $6$; in the last two test cases, the actual length of each line is $4$. In a typesetting scheme, the spaces between two adjacent sentences on the same line are counted in that line’s length (see the second dataset in the sample). There is no trailing space at the end of a line. #### Constraints | Test Point | $T$ | $N$ | $L$ | $P$ | | :-: | :-: | :-: | :-: | :-: | | $1$ | $\le 10$ | $\le 18$ | $\le 100$ | $\le 5$ | | $2$ | ^ | $\le 2\times 10^3$ | $\le 6\times 10^4$ | $\le 10$ | | $3$ | ^ | ^ | ^ | ^ | | $4$ | $\le 5$ | $\le 10^5$ | $\le 200$ | ^ | | $5$ | ^ | ^ | ^ | ^ | | $6$ | ^ | ^ | $\le 3\times 10^6$ | $2$ | | $7$ | ^ | ^ | ^ | ^ | | $8$ | ^ | ^ | ^ | $\le 10$ | | $9$ | ^ | ^ | ^ | ^ | | $10$ | ^ | ^ | ^ | ^ | The length of every sentence does not exceed $30$. Translated by ChatGPT 5