Description

Maryam 和 Peiling 最近在练习一个新的数字魔术，他们需要你的帮助来做到最好。这个魔术的流程如下：Maryam 首先独立随机地选择 $N$ 个整数，每个数都在 $2$ 到 $M$ 之间（包含 $2$ 和 $M$），每个数出现的概率均等，并将这 $N$ 个数分别写在 $N$ 张卡片上。注意，有些数字可能相同。然后，她重复以下过程 $K$ 次：从所有卡片中随机选取一个子集（每张卡片被选中的概率为 $0.5$），并写下这些卡片上数字的乘积。完成所有操作后，她将这 $K$ 个乘积展示给 Peiling，Peiling 的目标是仅根据 $N$、$M$ 和这些乘积，猜出最初 Maryam 选的 $N$ 个数字。

举个例子，若 $N=3$，$M=4$，$K=4$，Maryam 随机选出 $3$ 个 $2$ 到 $4$ 之间的整数——假设她选的是 $A_1=3$，$A_2=3$，$A_3=4$。然后，她计算这三个数的四个随机子集的乘积。例如，这些乘积可能是 $A_1 \cdot A_2=9$，$A_3=4$，$A_1 \cdot A_2 \cdot A_3=36$，以及 $1=1$（最后一个乘积是空集的乘积，所以等于 $1$）。Peiling 收到的数字是 $9$、$4$、$36$、$1$，并且知道 $N=3$、$M=4$。在这种情况下，仅凭数字 $36$ 就足以推断原始数字，因为只有 $3 \cdot 3 \cdot 4$ 能表示为三个不超过 $4$ 的数的乘积。因此 Peiling 猜测原始数字为 $3$、$3$ 和 $4$，观众们都为此惊叹。

在其他情况下，猜出原始数字就没那么简单了。例如，所有乘积可能全为 $1$。这种情况下无法推断出任何信息，Peiling 也无法总是猜对。然而，Peiling 知道 Maryam 一定严格按照上述流程操作：首先独立等概率地选出 $N$ 个 $2$ 到 $M$ 之间的整数，然后独立等概率地从每个数中以 $0.5$ 的概率加入到每个子集中，共选出 $K$ 个子集。请你利用这些信息，帮助 Peiling 做出更好的猜测！

这道题在 Code Jam 中有些特别。你会得到 $R$ 组独立的 $K$ 个数字，每组都需要输出一个答案——这部分和以往一样。不过，你并不需要全部猜对！只要你猜对至少 $X$ 组（具体 $X$ 见下方数据范围），你的解答就会被判定为正确。但无论结果如何，你都必须严格按照输出格式输出每组答案。唯一允许的错误就是输出的数字不对；但每组必须输出恰好 $N$ 个数字，且每个数字都在 $2$ 到 $M$ 之间。

由于本题涉及随机性，即使是最优解法在某些输入下也可能无法猜对 $X$ 组（比如所有乘积都为 $1$ 时）。因此，本题没有 Large 输入，而是提供了两个 Small 输入。你可以多次尝试 Small 输入（每次错误会有 4 分钟惩罚），并且只有通过第一个 Small 输入后才能尝试第二个。除此之外，Small 输入的流程和其他题目一样。

祝你好运！

Input Format

输入的第一行为测试用例数 $T$，始终为 $1$。第二行包含四个用空格分隔的整数 $R$、$N$、$M$ 和 $K$。接下来 $R$ 行，每行包含 $K$ 个整数，表示 Maryam 给 Peiling 的一组乘积。保证所有输入数据均严格按照题面流程独立随机生成。

Output Format

第一行输出 "Case #1:"。之后的每一行输出 $N$ 个数字，表示你对 Maryam 隐藏数字的猜测。每组输出顺序任意，但必须恰好 $N$ 个数字，且每个数字在 $2$ 到 $M$ 之间（注意 $M<10$，所有数字都是一位数）。数字之间不要有空格。

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

Case #1:
343
222

Hint

样例说明

样例输入不符合任一数据范围。在样例输入中，你需要至少猜对 $X=1$ 组。

在样例中，Maryam 第一次选的是 $3, 3, 4$，第二次选的是 $2, 4, 4$。样例输出中，Peiling 第一次猜对了，第二次没猜对。

第一个小数据集（10 分，测试集 1 - 可见）

• $T = 1$
• $R = 100$
• $N = 3$
• $M = 5$
• $K = 7$
• 你需要至少猜对 $X=50$ 组

第二个小数据集（31 分，测试集 2 - 可见）

• $T = 1$
• $R = 8000$
• $N = 12$
• $M = 8$
• $K = 12$
• 你需要至少猜对 $X=1120$ 组

翻译由 ChatGPT-4.1 完成。