JOICup 是 JOI 广播电台举办的一档广受欢迎的电视综艺节目。现在 JOICup 进入了决赛。在决赛中，将进行“信使游戏”。只有一支通过了初赛的队伍将参加该游戏。该队伍由两名选手 Anna 和 Bruno 组成。

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

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

1. 游戏主持人 Bitaro 给 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$）以及一个长度为 $N_i$、由 'A' 和 'B' 组成的字符串 $S_i$。网格中的所有格子初始均为白色。
2. Anna 给行号不等于 $X_i$ 且列号不等于 $Y_i$ 的 49 个格子涂色。每个格子的颜色要么是蓝色，要么是红色。
3. Anna 将网格交给游戏主持人 Bitaro。
4. Bitaro 给行号等于 $X_i$ 或列号等于 $Y_i$ 的 15 个格子涂色。每个格子的颜色要么是蓝色，要么是红色。此过程在 Anna 和 Bruno 看不到的房间中进行。
5. 游戏主持人 Bitaro 给 Bruno 一张卡片和网格。卡片上只写有整数 $N_i$。
6. Bruno 在纸上写下一个字符串。如果该字符串与 $S_i$ 一致，则 Anna 和 Bruno 赢得游戏。

挑战过程如下图所示：

挑战流程图

请编写实现 Anna 和 Bruno 策略的程序以赢得“信使游戏”。关于本任务的评分，请参阅评分说明。

实现细节

你需要提交两个文件。

第一个文件是 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 中给 Anna 的卡片上写的整数 $X_i$。
  • 参数 Y 是在第 $i$ 次挑战的步骤 1 中给 Anna 的卡片上写的整数 $Y_i$。
  • 参数 N 是在第 $i$ 次挑战的步骤 1 中给 Anna 的卡片上写的整数 $N_i$。
  • 参数 S 是在第 $i$ 次挑战的步骤 1 中给 Anna 的卡片上写的字符串 $S_i$。

  对于每次对 Anna 的函数调用，总共应调用 49 次以下函数。对于行号不等于 $X_i$ 且列号不等于 $Y_i$ 的 49 个格子，每个格子应调用一次该函数。

  • void Paint(int a, int b, int c)
    • 参数 a, b 表示 Anna 给行号为 a、列号为 b 的格子涂色。这里必须满足条件 $0 \le a \le 7, 0 \le b \le 7, a \neq X, b \neq Y$。如果不满足此条件，你的程序将被判为 Wrong Answer [1]。
    • 参数 c 表示 Anna 涂的颜色，如果 c = 0 则为蓝色，如果 c = 1 则为红色。这里必须满足 $0 \le c \le 1$。如果不满足此条件，你的程序将被判为 Wrong Answer [2]。
    • 如果函数 Paint 使用相同的参数 (a, b) 被调用超过一次，你的程序将被判为 Wrong Answer [3]。
    • 当函数 Anna 终止时，如果对 Paint 的函数调用次数不等于 49，你的程序将被判为 Wrong Answer [4]。

第二个文件是 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 中给 Bruno 的卡片上写的整数 $N_i$。
  • 参数 T 是一个 $8 \times 8$ 的二维数组，对应于第 $i$ 次挑战步骤 5 中给 Bruno 的网格。行号为 a（$0 \le a \le 7$）、列号为 b（$0 \le b \le 7$）的格子的颜色，若 T[a][b] = 0 则为蓝色，若 T[a][b] = 1 则为红色。
  • 返回值是 Bruno 在纸上写的字符串。
  • 如果返回值是长度为 44 或更长的字符串，你的程序将被判为 Wrong Answer [5]。
  • 返回值的每个字符都应该是 'A' 或 'B'。如果不满足此条件，你的程序将被判为 Wrong Answer [6]。

说明

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

数据范围

• $1 \le Q \le 20\,000$。
• $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$）是长度为 $N_i$、由 'A' 和 'B' 组成的字符串。

评分说明

如果你的程序在任何测试用例中被判为任何类型的 Wrong Answer [1]–[6]（参见实现细节）或任何类型的运行时错误（TLE、MLE、异常终止等），你的得分均为 0 分，无论你的程序在其他测试用例中是否获胜。

否则，令 $L^*$ 为本任务所有测试用例中以下值的最小值。你的得分根据下表计算：

• $L$ 的最大值，使得 Anna 和 Bruno 在满足 $N_i \le L$ 的所有挑战中获胜。但是，如果他们在测试用例的所有挑战中都获胜，我们设 $L = 43$。

样例

输入格式 1

2
0 0 1 B
5 7 8 AAAABBBB

输出格式 1

(程序运行结果)

说明

在此样例输入中，有 $Q (= 2)$ 次挑战。

• 在第一次挑战中，$X_1 = 0, Y_1 = 0, N_1 = 1, S_1 = \text{“B”}$。Anna 给行号不等于 0 且列号不等于 0 的 49 个格子涂色。
• 在第二次挑战中，$X_2 = 5, Y_2 = 7, N_2 = 8, S_2 = \text{“AAAABBBB”}$。Anna 给行号不等于 5 且列号不等于 7 的 49 个格子涂色。

例如，如果你的程序在第一次挑战中调用了 Paint(0, 2, 1)，它将被判为 Wrong Answer [1]，因为它指定了一个行号为 0 的格子。

输入格式 2

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

输出格式 2

(程序运行结果)