题目描述

如果你想购买一部新的手机，市面上有许多不同类型的手机可供选择。为了决定哪一款最适合你，你需要考虑几个重要因素：尺寸和重量、电池容量、WAP支持、颜色、价格。其中一个最重要的因素是手机提供的游戏列表。诺基亚是最成功的手机制造商之一，因为它著名的游戏《贪吃蛇》和《贪吃蛇II》。ACM希望制造并销售自己的手机，并需要为其编程几款游戏。其中之一是《Master-Mind》，这是一款著名的棋盘逻辑游戏。

游戏由两名玩家进行。其中一名玩家选择一个由$P$个有序的针组成的秘密代码，每个针的颜色来自预定义的$C$种颜色。第二名玩家的目标是猜出这个秘密的颜色序列。某些颜色可能不会出现在代码中，某些颜色可能会出现多次。

玩家进行猜测，猜测的形式与秘密代码相同。每次猜测后，玩家会得到一个关于猜测成功程度的信息，称为提示。每个提示由$B$个黑点和$W$个白点组成。黑点表示每个被正确猜测的针，即颜色和位置都正确。白点表示颜色正确但位置错误。例如，如果秘密代码是“白色、黄色、红色、蓝色、白色”，而猜测是“白色、红色、白色、白色、蓝色”，则提示将包含1个黑点（第一个位置的白色）和3个白点（其他白色、红色和蓝色）。目标是用最少的提示次数猜出序列。

新的ACM手机应该能够扮演两种角色。它可以生成秘密代码并给出提示，也可以进行自己的猜测。你的目标是编写一个程序来处理后一种情况，即编写一个程序来生成Master-Mind的猜测。

输入格式

第一行是一个正整数$T$，表示测试用例的数量。每个测试用例描述一个游戏场景，你需要生成一个猜测。每个测试用例的第一行是三个整数$P$、$C$和$M$。$P$（$1 \leq P \leq 10$）是针的数量，$C$（$1 \leq C \leq 100$）是颜色的数量，$M$（$1 \leq M \leq 100$）是已经进行的猜测次数。

接下来是$2 \times M$行，每两个行对应一个猜测。每个猜测的第一行是$P$个整数，表示猜测的颜色。每个颜色用一个数字$G_i$表示，$1 \leq G_i \leq C$。第二行是两个整数$B$和$W$，表示对应提示的黑点和白点数量。

假设秘密代码为$S_1, S_2, \ldots, S_P$，猜测为$G_1, G_2, \ldots, G_P$。我们可以构造一个集合$H$，包含满足$S_I = G_J$的数对$(I,J)$，且每个数字在第一个位置和第二个位置最多出现一次。也就是说，对于集合中的任意两个不同的数对$(I_1,J_1)$和$(I_2,J_2)$，有$I_1 \neq I_2$和$J_1 \neq J_2$。然后，$B(H)$表示集合中满足$I = J$的数对数量，$W(H)$表示满足$I \neq J$的数对数量。

我们定义两个可能的集合$H_1$和$H_2$的排序。我们说$H_1 \leq H_2$当且仅当以下条件之一成立：

1. $B(H_1) < B(H_2)$，或
2. $B(H_1) = B(H_2)$且$W(H_1) \leq W(H_2)$。

然后我们可以找到一个最大的集合$H_{\text{max}}$。$B(H_{\text{max}})$和$W(H_{\text{max}})$就是该提示的黑点和白点数量。

输出格式

对于每个测试用例，输出一行包含$P$个数字，表示下一个猜测的颜色。你的猜测必须与之前的所有猜测和提示一致。如果序列未被之前的猜测和提示排除，则该猜测是有效的。

如果没有有效的猜测，输出You are cheating!。如果有多个有效猜测，输出字典序最小的那个。即找到这样的猜测$G$，使得对于其他任何有效猜测$V$，存在一个数字$I$满足：

1. 对于所有$J < I$，$G_J = V_J$，且
2. $G_I < V_I$。

示例输入

3
4 3 2
1 2 3 2
1 1
2 1 3 2
1 1
4 6 2
3 3 3 3
3 0
4 4 4 4
2 0
8 9 3
1 2 3 4 5 6 7 8
0 0
2 3 4 5 6 7 8 9
1 0
3 4 5 6 7 8 9 9
2 0

示例输出

1 1 1 3
You are cheating!
9 9 9 9 9 9 9 9

来源

Central Europe 2000