The Number Trick

Maryam and Peiling are practicing a number trick.

Maryam first picks $N$ integers independently and uniformly at random from 2 to $M$, and writes one of them on each of $N$ cards. The same number may appear several times. She then repeats the following $K$ times: she takes each of the $N$ cards independently with probability $1/2$ to form a subset, and writes down the product of the numbers on the cards she took. If she takes no card, the product is 1.

Maryam tells Peiling the $K$ products together with $N$ and $M$. Peiling has to name the $N$ hidden numbers.

Peiling cannot always be right. When every product is 1, the products say nothing about the hidden numbers. So Peiling names the collection of $N$ numbers that is most likely given the products she saw. Your program computes exactly that answer for each of $R$ independent groups of products.

Here is the same rule as a formula. Let $A$ be a multiset of $N$ integers from 2 to $M$.

• $W(A)$ is the number of ordered $N$-tuples whose multiset is $A$. If $v$ occurs $f_v$ times in $A$, then $W(A) = N! / \prod_{v=2}^{M} f_v!$.
• $c_A(p)$ is the number of subsets whose product is $p$ when the cards carry $A$. There are $2^N$ subsets in total, and two cards are distinct even when they carry the same number.

If one group of products is $P_1, \dots, P_K$, the score of $A$ is

$S(A) = W(A) \times \prod_{j=1}^{K} c_A(P_j)$

$S(A)$ is proportional to the posterior probability that the hidden multiset is $A$ once those products are observed. The answer for that group is therefore an $A$ that maximizes $S(A)$. Several multisets may reach the maximum, so take the one whose elements, listed in non-decreasing order, form the lexicographically smallest string.

The first line contains the number of test cases $T$. $T$ is always 1.

The second line contains the integers $R$, $N$, $M$, $K$ separated by spaces.

Each of the next $R$ lines contains the $K$ products of one group, separated by spaces.

Limits

• $T = 1$
• $1 \le R \le 100$
• $1 \le N \le 12$
• $2 \le M \le 8$
• $1 \le K \le 12$
• Every given product is at least 1 and at most $M^N$.
• For every group there is at least one multiset $A$ with $c_A(P_j) \ge 1$ for all $j$, so a candidate with a positive score always exists.

Print "Case #1:" on the first line.

Then print $R$ lines. Line $i$ holds the answer for group $i$, that is the lexicographically smallest multiset among those maximizing $S(A)$, printed as $N$ digits. Write the digits in non-decreasing order with no spaces between them. Each digit is between 2 and $M$. Since $M < 10$, every hidden number has one digit.