题目背景

在洛谷上提交时，只提交一个文件。

在文件头粘贴如下的内容：

void Paint(int a, int b, int c);

不要引入任何头文件，并使用 C++20 提交。

由于交互库实现方式的原因，将时限改为 6s。

题目描述

JOICup 是由 JOI 电视台举办的人气综艺节目。现在 JOICup 进入了最终轮。在最终轮中将进行 “messenger game（信使游戏）”。只有通过第一轮的一支队伍会进行游戏。该队伍由两名选手组成，Anna 和 Bruno。

在信使游戏中，选手们使用一张 $8 \times 8$ 的网格来传递信息。网格的行编号为 $0$ 到 $7$，列编号为 $0$ 到 $7$。

在信使游戏中，Anna 和 Bruno 被隔离在不同的房间。他们将进行 $Q$ 次挑战。第 $i$ 次挑战（$1 \le i \le Q$）按如下流程进行。

1. 主持人 Bitato 给 Anna 一张卡片和一张 $8 \times 8$ 的网格。卡片上写有三个整数 $X_i, Y_i, N_i$（$0 \le X_i \le 7$，$0 \le Y_i \le 7$，$1 \le N_i \le 43$）以及一个由 A 和 B 组成、长度为 $N_i$ 的字符串 $S_i$。网格上所有单元格最初均为白色。
2. Anna 给满足 “行不等于 $X_i$ 且列不等于 $Y_i$” 的 $49$ 个单元格分别上色。每个被上色的单元格颜色要么是蓝色，要么是红色。
3. Anna 将这张网格交给主持人 Bitato。
4. Bitato 将满足 “行等于 $X_i$ 或列等于 $Y_i$” 的 $15$ 个单元格分别上色。每个被上色的单元格颜色要么是蓝色，要么是红色。此步骤在 Anna 和 Bruno 都看不到的房间内完成。
5. 主持人 Bitato 将一张卡片和网格交给 Bruno。卡片上只写有整数 $N_i$。
6. Bruno 在纸上写下一个字符串。如果它与 $S_i$ 完全一致，Anna 和 Bruno 就赢得这次游戏。

挑战流程如下图所示。

请编写程序，实现 Anna 和 Bruno 的策略，从而赢得 “messenger game”。有关本题的评分方法，请参见下文 “评分”。

实现细节（Anna.cpp）

你需要提交两个文件。第一个文件是 Anna.cpp，用于实现 Anna 的策略，需实现下列函数。程序应通过预处理指令 #include 包含 Anna.h。

• void Anna(int X, int Y, int N, std::string S)
  该函数被调用 $Q$ 次。第 $i$ 次调用（$1 \le i \le Q$）对应第 $i$ 次挑战的步骤 1、2、3。
  • 参数 $X$ 为第 $i$ 次挑战步骤 1 中卡片上写的整数 $X_i$。
  • 参数 $Y$ 为第 $i$ 次挑战步骤 1 中卡片上写的整数 $Y_i$。
  • 参数 $N$ 为第 $i$ 次挑战步骤 1 中卡片上写的整数 $N_i$。
  • 参数 $S$ 为第 $i$ 次挑战步骤 1 中卡片上写的字符串 $S_i$。

对每次调用 Anna，以下函数总计应被调用 $49$ 次。应对恰好那 $49$ 个 “行不等于 $X_i$ 且列不等于 $Y_i$” 的单元格各调用一次下列函数。

• void Paint(int a, int b, int c)
  • 参数 $a, b$ 表示 Anna 给第 $a$ 行第 $b$ 列的单元格上色。必须满足 $0 \le a \le 7$，$0 \le b \le 7$，$a \ne X$，$b \ne Y$。若不满足，则判为 Wrong Answer [1]。
  • 参数 $c$ 表示上色的颜色：当 $c = 0$ 时为蓝色，当 $c = 1$ 时为红色。必须满足 $0 \le c \le 1$。若不满足，则判为 Wrong Answer [2]。
  • 若对相同的 $(a, b)$ 多次调用 Paint，则判为 Wrong Answer [3]。
  • 当 Anna 函数结束时，若调用 Paint 的次数不是 $49$，则判为 Wrong Answer [4]。

实现细节（Bruno.cpp）

第二个文件是 Bruno.cpp，用于实现 Bruno 的策略，需实现下列函数。程序应通过预处理指令 #include 包含 Bruno.h。

• std::string Bruno(int N, std::vector<std::vector<int>> T)
  • 每当 Anna 完成网格上色后调用一次此函数。总计调用 $Q$ 次。第 $i$ 次调用（$1 \le i \le Q$）对应第 $i$ 次挑战的步骤 5、6。
  • 参数 $N$ 为第 $i$ 次挑战步骤 5 中卡片上写的整数 $N_i$。
  • 参数 $T$ 为大小为 $8 \times 8$ 的二维数组，对应第 $i$ 次挑战步骤 5 中交给 Bruno 的网格。若行号为 $a$（$0 \le a \le 7$）且列号为 $b$（$0 \le b \le 7$）的单元格颜色为蓝色，则有 $\texttt{T[a][b] = 0}$；若为红色，则有 $\texttt{T[a][b] = 1}$。
  • 返回值为 Bruno 写在纸上的字符串。
  • 若返回值的长度不少于 $44$，则判为 Wrong Answer [5]。
  • 返回值的每个字符必须是 ‘A’ 或 ‘B’。若不满足，则判为 Wrong Answer [6]。

重要注意事项

• 你的程序可以实现其他供内部使用的函数，或使用全局变量。提交的文件将与评测器一同编译，生成单一的可执行文件。为避免与其他文件冲突，所有全局变量和内部函数应声明在匿名命名空间中。评测时将以 Anna 和 Bruno 两个进程的形式运行。Anna 进程与 Bruno 进程不能共享全局变量。
• 你的程序不得使用标准输入与标准输出。你的程序不得通过任何方式与其他文件通信。不过，你可以向标准错误输出调试信息。

编译与本地测试

你可以从竞赛网页下载包含样例评测器的压缩包以测试你的程序。压缩包中也包含示例程序源码。

样例评测器文件为 grader.cpp。要测试你的程序，请将 grader.cpp、Anna.cpp、Bruno.cpp、Anna.h、Bruno.h 放在同一目录下，并运行以下命令进行编译。你也可以运行压缩包内的 compile.sh。

g++ -std=gnu++17 -O2 -o grader grader.cpp Anna.cpp Bruno.cpp

编译成功后会生成可执行文件 grader。需要注意，实际评测器与样例评测器不同。特别地，Bitaro 不一定随机给单元格上色。样例评测器将以单进程方式运行，从标准输入读取数据并将结果输出到标准输出。

输入格式

样例评测器从标准输入读取如下数据。

$Q$
$X_1$ $Y_1$ $N_1$ $S_1$
$X_2$ $Y_2$ $N_2$ $S_2$
$\vdots$
$X_Q$ $Y_Q$ $N_Q$ $S_Q$

输出格式

样例评测器向标准输出输出如下信息（为便于说明加了引号）。

• 若你的程序被判定为正确，它会输出 $L^*$ 的值，如 “$\texttt{Accepted: 28}$”。关于 $L^*$ 的定义，见下文 “评分”。
• 若你的程序被判定为任一种 Wrong Answer，它会输出对应类型，如 “$\texttt{Wrong Answer [1]}$”。

如果你的程序同时满足多种 Wrong Answer 的判定条件，样例评测器只报告其中一种。

在样例评测器中，每次挑战中 Bitaro 选择颜色是由伪随机数决定的，不同次执行的结果不变。要更改伪随机数的种子，请按如下方式以一个整数参数运行样例评测器。

./grader 2023

提示

约束

• $1 \le Q \le 20000$。
• $0 \le X_i \le 7$（$1 \le i \le Q$）。
• $0 \le Y_i \le 7$（$1 \le i \le Q$）。
• $1 \le N_i \le 43$（$1 \le i \le Q$）。
• $Q, X_i, Y_i, N_i$ 为整数。
• $S_i$（$1 \le i \le Q$）为由 ‘$\texttt{A}$’ 与 ‘$\texttt{B}$’ 组成、长度为 $N_i$ 的字符串。

评分

若你的程序在任一测试用例中出现实现细节部分的 Wrong Answer [1]–[6] 或任意运行时错误（TLE、MLE、异常结束等），则无论在其他测试用例中是否赢得挑战，得分均为 $0$。否则，令 $L^*$ 为对本题所有测试用例取下述值的最小值。你的得分按下表计算。

• $L$ 的定义为：使得当 $N_i \le L$ 时，Anna 与 Bruno 能赢得所有挑战的最大值。但若他们在全部测试用例中都赢得了所有挑战，则令 $L = 43$。

$L^*$	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
Score	0	5	8	10	11	13	14	16	18	19	21	22	24	26	27

$L^*$	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29
Score	29	30	32	34	35	37	38	40	42	43	45	46	48	50	51

$L^*$	30	31	32	33	34	35	36	37	38	39	40	41	42	43
Score	53	54	56	57	59	60	62	65	68	71	74	77	84	100

样例交互

下述是样例评测器的一组输入与对应的函数调用。为简洁起见，Bruno 的函数调用参数 $T$ 省略。

样例输入 1

2
0 0 1 B
5 7 8 AAAABBBB

样例函数调用

调用 Anna 的函数	调用 Bruno 的函数	Bruno 的返回值
$\texttt{Anna(0, 0, 1, "B")}$
$\texttt{Paint(1, 1, 0)}$
$\texttt{Paint(1, 2, 1)}$
$\vdots$
$\texttt{Paint(7, 7, 1)}$
	$\texttt{Bruno(1, ...)}$	$\texttt{"B"}$
$\texttt{Anna(5, 7, 8, "AAAABBBB")}$
$\texttt{Paint(0, 0, 1)}$
$\texttt{Paint(0, 1, 1)}$
$\vdots$
$\texttt{Paint(7, 6, 0)}$
	$\texttt{Bruno(8, ...)}$	$\texttt{"AAAABBBB"}$

在这组样例输入中，有 $Q = 2$ 次挑战。

• 第一次挑战中，$X_1 = 0$，$Y_1 = 0$，$N_1 = 1$，$S_1 = \texttt{"B"}$。Anna 给所有 “行不为 $0$ 且列不为 $0$” 的 $49$ 个单元格上色。
• 第二次挑战中，$X_2 = 5$，$Y_2 = 7$，$N_2 = 8$，$S_2 = \texttt{"AAAABBBB"}$。Anna 给所有 “行不为 $5$ 且列不为 $7$” 的 $49$ 个单元格上色。

例如，若你的程序在第一次挑战中调用了 $\texttt{Paint(0, 2, 1)}$，则因为其指定了行号为 $0$ 的单元格而被判为 Wrong Answer [1]。

这里还给出样例评测器的另一组输入。

30
3 1 1 A
1 4 1 A
6 6 2 AA
1 1 2 BB
3 1 3 BAB
7 4 3 AAB
6 4 4 BAAB
6 7 4 BABA
3 3 5 BABBA
1 5 5 ABBBA
4 3 6 ABBBBB
2 1 6 ABAAAA
6 0 7 AAABABA
6 6 7 BBABBAA
0 4 8 AABAABAB
2 1 8 AABBBBBA
2 0 9 BABABBAAA
1 5 9 BBAAABABB
6 7 10 BAAABAAABB
1 7 10 BBBBBBBABA
2 6 12 AABAABABABAB
3 4 15 BBAABAAAABABAAB
5 6 18 BAAAABBABABBBABBAB
7 0 22 BABBAABAAABBABBBBBBABA
2 0 26 AAAABBABBAAAAABABABBAABAAA
0 7 30 AAABBBAAABAABBBBAABBAAABBBABBB
2 7 34 BABAABBAABABBABAABBABBABAABBBBABBB
2 5 38 BBBBAABAABAABABABBBBBAAABBABAAABAAABBB
5 2 41 AABABBAAABBABAAAABBABABBAAAAAABBABBABBABA
1 0 43 AABBABBBBABABBBABBBBAAAAAABABAAABBBAABBAAAB