숫자 카드 마술

마리암과 페이링이 숫자 마술을 연습한다. 마술은 이렇게 진행된다.

마리암은 먼저 $2$ 이상 $M$ 이하인 정수 $N$개를 고른다. 각 수는 서로 독립이고, 가능한 값은 모두 같은 확률로 나온다. 고른 수는 카드 $N$장에 하나씩 적으며, 같은 수가 여러 번 나오기도 한다. 그다음 아래 과정을 $K$번 반복한다. 카드마다 확률 $0.5$로 독립하게 뽑아 부분집합을 만들고, 그 부분집합에 적힌 수의 곱을 적는다. 카드를 하나도 뽑지 않았다면 곱은 $1$이다.

마리암은 이렇게 얻은 곱 $K$개를 페이링에게 보여준다. 페이링은 $N$, $M$, $K$와 곱 $K$개만 보고 카드에 적힌 수를 맞혀야 한다.

곱만으로 원래 수가 하나로 정해지지 않는 경우가 많다. 곱이 모두 $1$이면 카드에 대한 정보가 아예 없다. 그래서 이 문제는 사후 확률이 가장 큰 후보를 답으로 요구한다.

$2 \le B_1 \le B_2 \le \dots \le B_N \le M$인 수열 $B$를 후보라고 하자. 관측한 곱을 $P_1, P_2, \dots, P_K$라 하고, $c_B(p)$를 원소의 곱이 $p$인 $\{1, 2, \dots, N\}$의 부분집합 개수라고 하자. 공집합의 곱은 $1$이다. $o(B)$는 $B$의 원소를 나열하는 서로 다른 순서의 개수로, 값 $v$가 $B$에 $m_v$번 나오면 $o(B) = N! / \prod_v m_v!$이다. 후보의 무게를 다음과 같이 정의한다.

$W(B) = o(B) \times \prod_{j=1}^{K} c_B(P_j)$

$W(B)$는 관측한 곱이 주어졌을 때 마리암이 고른 수의 모임이 $B$일 확률에 비례한다.

각 세트마다 $W(B)$가 가장 큰 후보를 출력한다. 그런 후보가 여럿이면 사전순으로 가장 앞서는 것을 출력한다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. $T$는 항상 $1$이다. 둘째 줄에 네 정수 $R$, $N$, $M$, $K$가 공백으로 구분되어 주어진다. 이어지는 $R$개 줄에 각각 곱 $K$개가 공백으로 구분되어 주어진다. 각 줄은 마리암이 위 절차대로 만든 서로 독립인 세트 하나다.

첫째 줄에 "Case #1:"을 출력한다. 이어서 $R$개 줄에 각 세트의 답을 순서대로 출력한다. 한 줄에는 숫자 $N$개를 오름차순으로 공백 없이 붙여 쓴다. $M < 10$이므로 모든 수는 한 자리다.

• $T = 1$
• $1 \le R \le 100$
• $1 \le N \le 6$
• $2 \le M \le 9$
• $1 \le K \le 10$
• 모든 입력은 문제의 절차대로 만들어졌다. 즉 각 $P_j$는 그 세트의 숨은 수 가운데 어떤 부분집합의 곱이다.

첫 번째 예제의 첫 세트는 $N = 3$, $M = 4$이고 곱 가운데 $36$이 있다. $2$ 이상 $4$ 이하인 수 셋의 곱으로 $36$을 만드는 방법은 $3 \times 3 \times 4$ 하나뿐이므로 답은 334이다. 둘째 세트는 곱이 모두 $1$이라 모든 후보의 $c_B(1)$이 $1$로 같다. 이때는 $o(B)$가 큰 후보가 이긴다. 서로 다른 세 수를 고른 후보의 $o(B) = 6$이 가장 크고, 그중 사전순으로 가장 앞선 234가 답이다.