숫자 마술 알아맞히기

마리암과 페이링은 숫자 마술을 연습한다.

마리암은 먼저 2 이상 $M$ 이하의 정수 $N$개를 서로 독립적으로 균등하게 뽑아 카드 $N$장에 하나씩 적는다. 같은 수가 여러 번 나올 수 있다. 그다음 아래 과정을 $K$번 반복한다. 카드 $N$장을 각각 확률 $1/2$로 독립적으로 골라 부분집합을 만들고, 고른 카드에 적힌 수의 곱을 적어 둔다. 한 장도 고르지 않았다면 곱은 1이다.

마리암은 이렇게 얻은 곱 $K$개와 $N$, $M$을 페이링에게 알려 준다. 페이링은 숨겨진 수 $N$개를 맞혀야 한다.

페이링이 항상 맞힐 수는 없다. 곱이 모두 1이면 숨겨진 수에 관한 정보가 하나도 없다. 그래서 페이링은 자기가 본 곱을 바탕으로 가장 그럴듯한 수 $N$개의 모음을 답한다. 프로그램은 서로 독립인 곱 묶음 $R$개마다 그 답을 정확히 계산해야 한다.

수식으로 정리하면 이렇다. $A$를 2 이상 $M$ 이하의 정수 $N$개로 이루어진 중복집합이라 하자.

• $W(A)$는 중복집합이 $A$가 되는 순서 있는 $N$-튜플의 개수이다. $A$에서 $v$가 $f_v$번 나온다면 $W(A) = N! / \prod_{v=2}^{M} f_v!$이다.
• $c_A(p)$는 카드에 $A$가 적혀 있을 때 곱이 $p$인 부분집합의 개수이다. 부분집합은 모두 $2^N$개이고, 적힌 수가 같아도 카드는 서로 구별한다.

한 묶음의 곱이 $P_1, \dots, P_K$일 때 $A$의 점수는 다음과 같다.

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

$S(A)$는 그 곱을 관측했을 때 숨겨진 중복집합이 $A$일 사후확률에 비례한다. 따라서 그 묶음의 답은 $S(A)$를 최대로 만드는 $A$이다. 최댓값에 이르는 $A$가 여럿일 수 있으므로, 원소를 오름차순으로 늘어놓은 문자열이 사전순으로 가장 앞서는 것을 고른다.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다. $T$는 항상 1이다.

둘째 줄에 정수 $R$, $N$, $M$, $K$가 공백으로 구분되어 주어진다.

이어지는 $R$개의 줄에는 한 묶음의 곱 $K$개가 공백으로 구분되어 주어진다.

제한

• $T = 1$
• $1 \le R \le 100$
• $1 \le N \le 12$
• $2 \le M \le 8$
• $1 \le K \le 12$
• 주어지는 곱은 모두 1 이상 $M^N$ 이하이다.
• 묶음마다 모든 $j$에 대하여 $c_A(P_j) \ge 1$을 만족하는 중복집합 $A$가 적어도 하나 있다. 즉 점수가 양수인 후보가 항상 존재한다.

"Case #1:"을 첫째 줄에 출력한다.

이어서 $R$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 묶음의 답, 곧 $S(A)$가 최대인 중복집합 가운데 사전순으로 가장 앞서는 것을 숫자 $N$개로 출력한다. 숫자는 오름차순으로 붙여 쓰고 사이에 공백을 넣지 않는다. 각 숫자는 2 이상 $M$ 이하이다. $M < 10$이므로 숨겨진 수는 모두 한 자리이다.