I-Keyboard

Writing text on an old mobile-phone keypad can be tedious: with only a few keys available, most keys carry several letters, and you often have to press one key several times to type a single letter. A typical keypad has only twelve keys, and just eight of them are used to type the 26 letters of the English alphabet. The standard layout groups the letters like this:

 1         2 abc      3 def
 4 ghi     5 jkl      6 mno
 7 pqrs    8 tuv      9 wxyz
 *         0 space    #

On such a key, the first letter of the group needs one press, the second needs two presses, and so on. This layout spreads the letters evenly across the keys but ignores how often each letter is used. Because some letters are far more common than others, a frequent letter placed in the third or fourth position is expensive to type. For example, "s" is common in English yet needs four presses on the standard layout. A layout tuned to letter frequency, such as the one below, is much more comfortable for ordinary text:

 1         2 abcd     3 efg
 4 hijk    5 lm       6 nopq
 7 rs      8 tuv      9 wxyz
 *         0 space    #

Your task is to compute an optimal layout for a given set of letter frequencies. The letters must keep their original (alphabetical) order, because the user would be confused if they were shuffled, but you may assign any number of consecutive letters to a single key.

The first line contains a single positive integer T, the number of test cases.

Each test case starts with a line containing two integers K and L (1 ≤ K ≤ L ≤ 90) separated by one space, where K is the number of keys and L is the number of letters to place on those keys.

The next line contains exactly K characters, the names of the keys. The line after it contains exactly L characters, the names of the letters. Every key name and every letter name is a printable character with ASCII code from 33 to 126 inclusive. All key names are distinct and all letter names are distinct, but the same character may be used both as a key name and as a letter name.

After those two lines come exactly L lines; the i-th of them contains a positive integer Fi, the frequency of the i-th letter in the given order. A larger value means a more common letter. No frequency exceeds 100000.

For each test case, build an optimal keyboard: one whose total typing price is as small as possible. The price of a letter is its frequency multiplied by its position on the key (1 for the first letter of the key, 2 for the second, and so on), and the total price is the sum over all letters. The letters keep their given order and are split into consecutive groups, one group per key.

Formally, find positions P1, P2, …, PL such that:

• P1 = 1;
• for every i > 1, either Pi = Pi−1 + 1 or Pi = 1;
• at most K of the values Pi equal 1;
• the total price SP = Σ (1 ≤ i ≤ L) Fi · Pi is minimal;
• among all sequences with the same minimal price, the chosen one assigns as many letters as possible to the last key, then to the key before it, and so on. Equivalently, for any other valid sequence Q with the same total price there is an index M with PJ = QJ for all J > M and PM > QM.

Because K ≤ L, an optimal keyboard always uses all K keys, so every key receives at least one letter.

For each test case, first print a line "Keypad #I:", where I is the test-case number starting from 1. Then print exactly K lines, one per key in input order; each line contains the key's character, a colon, a single space, and the letters assigned to that key written together with no separators. Print a blank line between consecutive test cases.