题目描述

拉丁方阵是一个 $3 \times 3$ 的网格，由字母 $\texttt{A}$、$\texttt{B}$ 和 $\texttt{C}$ 组成，满足以下条件：

• 每一行中，字母 $\texttt{A}$、$\texttt{B}$ 和 $\texttt{C}$ 各出现一次；
• 每一列中，字母 $\texttt{A}$、$\texttt{B}$ 和 $\texttt{C}$ 各出现一次。

例如，下面是一个可能的拉丁方阵：

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

现在，给你一个拉丁方阵，但其中有一个字母被问号 $\texttt{?}$ 替换了。请你找出被替换的字母。

输入格式

输入的第一行包含一个整数 $t$（$1 \leq t \leq 108$），表示测试用例的数量。

每个测试用例包含三行，每行包含三个字符，表示一个拉丁方阵。每个字符是 $\texttt{A}$、$\texttt{B}$、$\texttt{C}$ 或 $\texttt{?}$ 之一。

每个测试用例保证是一个拉丁方阵，且恰好有一个字母被问号 $\texttt{?}$ 替换。

输出格式

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

样例

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

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}$$

由 ChatGPT 4.1 翻译

来源

Codeforces 1915B，英文题名 Not Quite Latin Square。