Huffman Tree

One relatively simple way to compress data is to use a Huffman tree. With a Huffman tree you can easily compress the data in a file and later decompress it.

Many programs use a binary Huffman tree, in which every node is either a leaf or has exactly two children. This problem generalizes that idea to an $N$-ary Huffman tree, in which every internal node has exactly $N$ children.

If a file contains $Z$ distinct characters, the tree has exactly $Z$ leaves. The sequence of numbers written along the path from the root down to a leaf is the encoding of that character. Each edge (a step from a node to one of its children) is labeled with a number from $0$ to $N-1$.

Placing frequently used characters close to the root and rarely used characters far from it improves the compression ratio. In other words, a Huffman tree is a tree that minimizes the total number of $N$-ary symbols needed to encode the file.

In this problem, every node of the tree is either an internal node or a leaf that encodes exactly one character. There are no dangling leaves that encode no character, so every internal node has exactly $N$ children.

For example, when $N=3$, a frequently used character may be encoded with a single symbol, a less common one with two symbols, and a rare one with three symbols.

To decode a file you must know the tree that was used to encode it, so the tree has to be stored. In this problem the tree is stored as follows. The $Z$ distinct characters are denoted by the integers $0, 1, \dots, Z-1$. Write these characters once each in increasing order to form a file, encode that file, and store the resulting string. That is, the stored string is the encoding of character $0$, followed by the encoding of character $1$, and so on up to the encoding of character $Z-1$, all concatenated together.

Given $N$ and the string stored as above, write a program that determines the symbol sequence that encodes each character.

The first line contains the number of test cases $T$. Each test case consists of three lines:

• Line 1: the number of distinct characters in the file, $Z$ ($2 \le Z \le 20$).
• Line 2: the arity $N$ of the Huffman tree ($2 \le N \le 10$). The tree is $N$-ary: $N=2$ is binary and $N=3$ is ternary.
• Line 3: the string obtained by encoding the file that lists every character exactly once in increasing order. Its length does not exceed $200$, and every character is a digit from $0$ to $N-1$.

The same string may correspond to more than one tree. For example, when $Z=5$ and $N=2$, the string $010011101100$ can come from several different trees. However, only inputs whose answer is uniquely determined are given in this problem.

For each test case, print $Z$ lines. Each line has the form character->encoding, where the character is an integer from $0$ to $Z-1$ and the encoding is the symbol sequence assigned to that character by the Huffman tree. Print the characters in the order $0, 1, \dots, Z-1$.