Problem
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 A1=3, A2=3 and A3=4. Then, she calculates four products of random subsets of those three numbers. For example, let's say those products are A1A2=9, A3=4, A1A2A3=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 33*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!
Solving this problem
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!
Input
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.
Output
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.
Limits
Time limit: 60 20 seconds per test set.
Memory limit: 1GB.
First Small dataset (Test set 1 - Visible; 10 Points)
T = 1.
R = 100.
N = 3.
M = 5.
K = 7.
You need to get at least X=50 sets right.
Second Small dataset (Test set 2 - Visible; 31 Points)
T = 1.
R = 8000.
N = 12.
M = 8.
K = 12.
You need to get at least X=1120 sets right.
Sample
1 2 3 4 4 9 4 36 1 1 1 1 1
Case #1: 343 222
Note
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.