← 返回题目列表

Codeforces · 1915/B

B. 不完全是拉丁方

中文机器翻译题面 查看原题

拉丁方是由字母 $$$\texttt{A}$$$、$$$\texttt{B}$$$ 和 $$$\texttt{C}$$$ 组成的 $$$3 \times 3$$$ 网格,这样:

- 在每一行中,字母 $$$\texttt{A}$$$、$$$\texttt{B}$$$ 和 $$$\texttt{C}$$$ 各出现一次,并且
- 在每列中,字母 $$$\texttt{A}$$$、$$$\texttt{B}$$$ 和 $$$\texttt{C}$$$ 各出现一次。

给你一个拉丁方,但其中一个字母被问号 $$$\texttt{?}$$$ 替换。找到被替换的字母。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 108$$$) — 测试用例的数量。

每个测试用例包含三行,每行由三个字符组成,代表拉丁方。每个字符都是 $$$\texttt{A}$$$、$$$\texttt{B}$$$、$$$\texttt{C}$$$ 或 $$$\texttt{?}$$$ 之一。

每个测试用例都是一个拉丁方,其中恰好有一个字母被问号 $$$\texttt{?}$$$ 替换。

输出

对于每个测试用例,输出被替换的字母。

示例

输入 #1

3
ABC
C?B
BCA
BCA
CA?
ABC
?AB
BCA
ABC

输出 #1

A
B
C

注意

三个测试用例的正确拉丁方如下所示:

$$$$$$\begin{bmatrix} \texttt{A} & \texttt{B} & \texttt{C} \\ \texttt{C} & \color{red}{\texttt{A}} & \texttt{B} \\ \texttt{B} & \texttt{C} & \texttt{A} \\ \end{bmatrix} \quad \begin{bmatrix} \texttt{B} & \texttt{C} & \texttt{A} \\ \texttt{C} & \texttt{A} & \color{red}{\texttt{B}} \\ \texttt{A} & \texttt{B} & \texttt{C} \\ \end{bmatrix} \quad \begin{bmatrix} \color{red}{\texttt{C}} & \texttt{A} & \texttt{B} \\ \texttt{B} & \texttt{C} & \texttt{A} \\ \texttt{A} & \texttt{B} & \texttt{C} \\ \end{bmatrix}$$$$$$