题目描述

Maryam and Peiling have recently been practicing a new number trick, and they need your help to get it right. The trick goes as follows: Maryam starts by picking $N$ independent random integer numbers, each between 2 and $M$, inclusive, appearing with equal probability, and writes them down on $N$ cards, one number per card. Note that some numbers might be equal. Then, she repeats the following $K$ times: take a random subset of cards (each card is taken with probability 0.5), and write down the product of the numbers on those cards. Having done all that, she shows all $K$ products to Peiling, and Peiling's goal is to guess what the original $N$ numbers were, knowing just $N$, $M$, and the products.

An example game with $N=3$, $M=4$, $K=4$ might go like this: first, Maryam picks 3 random numbers between 2 and 4, inclusive - let's say she randomly chose $A_1=3$, $A_2=3$ and $A_3=4$. Then, she calculates four products of random subsets of those three numbers. For example, let's say those products are $A_1 \cdot A_2=9$, $A_3=4$, $A_1 \cdot A_2 \cdot A_3=36$, and $1=1$ (the last product has no numbers in it, so it's equal to 1). Peiling receives numbers 9, 4, 36, 1 from her, and she's also told that $N=3$ and $M=4$. In this case, just seeing the number 36 is enough to find what the original numbers were, since the only way to represent that as a product of up to 3 numbers, each up to 4, is $3 \cdot 3 \cdot 4$. So Peiling says that the original numbers were 3, 3 and 4, and the audience is impressed.

In some other cases, guessing the original numbers is not as simple. For example, it might happen that all products are equal to 1. In that case there is no way to know anything about the hidden numbers, so Peiling cannot always be right. However, Peiling knows that Maryam follows the procedure exactly as described above: she selects the first $N$ numbers as independent uniform integers between 2 and $M$, and then selects $K$ independent random subsets, picking each number into each subset independently with probability 0.5. Help Peiling use that knowledge to make better guesses!

This problem is a bit unusual for Code Jam. You will be given $R$ independent sets of $K$ numbers each, and should print an answer for each set — this part is as usual. However, you don't need to get all of your answers right! Your solution will be considered correct if answers for at least $X$ sets are correct, with the value of $X$ given in the Limits for the given input, below. However, you must follow the output format, even for sets in which your answer doesn't turn out to be correct. The only thing that can be wrong on any sets, yet still allow you to be judged correct, is the digits you output; but there should still be exactly $N$ digits printed for each case, and each digit must be between 2 and $M$.

This problem involves randomness, and thus it might happen that even the best possible solution doesn't make $X$ correct guesses (remember the situation when all products are equal to 1?) for a certain input. Because of that, this problem doesn't have a Large input, but instead has two Small inputs. That means you can try again if you think you got unlucky. You may only attempt to solve the second Small input once you have solved the first one. Otherwise, both Small inputs work in the same way as Small inputs for any other problem: you may try multiple times, and there is a 4-minute penalty for incorrect submissions if you later solve that input, even if the only reason you got it wrong was chance.

Good luck!

输入格式

The first line of the input gives the number of test cases, $T$, which is always equal to 1. The second line of the input file contains four space-separated integers $R$, $N$, $M$ and $K$, in that order. The next $R$ lines describe one set of $K$ products each. Each of those lines contains $K$ space-separated integers — the products that Maryam passes to Peiling. It is guaranteed that all sets in the input are generated independently randomly according to the procedure from the problem statement.

输出格式

On the first line, output "Case #1:". On each of the next $R$ lines output $N$ digits — your guess for Maryam's hidden numbers for the corresponding set of products. You can print the numbers for each set in any order, but there must be exactly $N$ digits, each between 2 and $M$, inclusive (note that $M<10$, so none of the numbers will be more than one digit). Do not put spaces between the digits.

1
2 3 4 4
9 4 36 1
1 1 1 1

Case #1:
343
222

提示

Sample Explanation

The sample input doesn't follow the limitations for either input. In the sample input, you need to get at least $X=1$ sets right.

In the sample input, Maryam picked the numbers $3, 3, 4$ the first time, and the numbers $2, 4, 4$ the second time. In the sample output, Peiling guessed correctly the first time, but not the second time.

First Small dataset (10 Pts, Test set 1 - Visible)

• $T = 1$.
• $R = 100$.
• $N = 3$.
• $M = 5$.
• $K = 7$.
• You need to get at least $X=50$ sets right.

Second Small dataset (31 Pts, Test set 2 - Visible)

• $T = 1$.
• $R = 8000$.
• $N = 12$.
• $M = 8$.
• $K = 12$.
• You need to get at least $X=1120$ sets right.