Find an optimal keyboard for each test case. Optimal keyboard is such that has the lowest "price" for typing average text. The price is determined as the sum of the prices of each letter. The price of a letter is a product of the letter frequency (Fi) and its position on the key. The order of letters cannot be changed, they must be grouped in the given order.
If there are more solutions with the same price, we will try to maximise the number of letters assigned to the last key, then to the one before the last one etc.
More formally, you are to find a sequence P1, P2, ... PL representing the position of every letter on a particular key. The sequence must meet following conditions:
P1 = 1
for each i>1, either Pi = Pi-1+1 or Pi = 1
there are at most K numbers Pi such that Pi = 1
the sum of products SP = F1*P1+F2*P2+...+FL*PL is minimal
for any other sequence Q meeting these criteria and with the same sum SQ = SP, there exists such M, 1 <= M <= L that for any J, M < J <= L, PJ = QJ, and PM > QM.
The output for every test case must start with a single line saying Keypad #I:, where I is a sequential order of the test case, starting with 1. Then there must be exactly K lines, each representing one letter, in the same order that was used in input. Each line must contain the character representing the key, a colon, one space and a list of letters assigned to that particular key. Letters are not separated from each other.
Print one blank line after each test case, including the last one.