P13806 [CERC 2022] Combination Locks

Alice 和 Bob 正在玩组合锁。每个人都有一个由 $N$ 个可旋转数字盘组成的组合锁，每个数字盘上刻有 $0$ 到 $9$ 的数字。他们的朋友 Charlie 没有锁，于是设计了一个游戏让他们消遣。他会记录他们锁上对应数字是否相同，并用一个差异模式字符串 $S$ 来描述当前情况。$S$ 的第 $j$ 个字符要么是 '='，要么是 '.'，分别表示 Alice 和 Bob 的锁的第 $j$ 个数字是否相同。 Charlie 负责裁判，Alice 和 Bob 轮流操作，Alice 先手。每次操作时，玩家必须改变自己组合锁上的一个数字。由于 Charlie 只记录差异模式，因此一次有效的操作必须使差异模式发生变化。他还非常迷信，带来了一份不能在游戏过程中出现的模式列表 $P_i$。Charlie 的主要任务是确保在游戏过程中没有差异模式重复出现。无法进行有效操作的玩家判负。 请编写程序判断如果双方都采取最优策略，谁将获胜。

第一行包含测试用例数 $T$。每个测试用例第一行包含两个用空格分隔的整数 $N$ 和 $C$。接下来两行分别描述 Alice 和 Bob 的组合锁初始状态，每个锁的状态是一个长度为 $N$ 的数字字符串。接下来的 $C$ 行，每行给出一个 Charlie 迷信的模式 $P_i$。迷信模式列表中没有重复，且保证初始锁状态对应的差异模式不在迷信模式列表中。

对于每个测试用例，输出一行，表示获胜者的名字。

### 说明 在第一个样例中，Alice 唯一的操作是将第二位数字从 2 改为 9。其他操作要么不会改变差异模式，要么会导致出现迷信模式。Bob 无法进行有效操作，因此 Alice 获胜。 ### 输入范围 - $1 \leq T \leq 20$ - $1 \leq N \leq 10$ - $0 \leq C \leq 1000$ 由 ChatGPT 4.1 翻译