Azzurro 和 Bordeaux 是一对在意大利赌场游玩的搭档，他们决定玩一个由荷官 Chiaro 提出的游戏。
在这个游戏中，信息通过一个 $N \times N$ 的网格（$N = 8$）进行传输。网格的行从上到下编号为 $0$ 到 $N - 1$，列从左到右编号为 $0$ 到 $N - 1$。行号为 $r$、列号为 $c$ 的单元格记作 $(r, c)$。
在这个游戏中，Azzurro 和 Bordeaux 被隔离在不同的房间里。他们将进行 $Q$ 轮游戏。第 $i$ 轮（$1 \le i \le Q$）的流程如下：
- Azzurro 从 Chiaro 那里收到一个整数 $N$，一个整数 $L_i$（$1 \le L_i \le 51$），一张写有长度为 $L_i$、由 'A' 和 'B' 组成的字符串 $S_i$ 的卡片，以及一个所有单元格均为白色的 $N \times N$ 网格。
- Azzurro 将 $N^2$ 个单元格中的每一个都涂成蓝色或红色。然后他将网格交给 Chiaro。
- Chiaro 在 Azzurro 和 Bordeaux 都看不见的情况下执行以下操作： (a) 他通过重复仅向相邻的下方或右方单元格移动，选择一条从 $(0, 0)$ 到 $(N - 1, N - 1)$ 的路径。 (b) 对于路径上的每一个单元格，如果该单元格是蓝色的，他将其重涂为红色；如果它是红色的，他将其重涂为蓝色。
- Bordeaux 从 Chiaro 那里收到一张写有整数 $N$ 和 $L_i$ 的卡片，以及该网格。
- Bordeaux 在一张纸上写下一个长度为 $L_i$、由 'A' 和 'B' 组成的字符串。如果写下的字符串与 $S_i$ 匹配，则 Azzurro 和 Bordeaux 获胜。
请编写程序来实现 Azzurro 和 Bordeaux 的策略以赢得此游戏。关于此任务的评分，请参阅“评分”部分。
实现细节
你需要提交两个文件。
第一个文件是 Azzurro.cpp。它应该实现 Azzurro 的策略。它应该实现以下函数。程序应使用预处理指令 #include 包含 Azzurro.h。
std::vector<std::vector<int>> Azzurro(int N, int L, std::string S)该函数会被调用 $Q$ 次。第 $i$ 次调用（$1 \le i \le Q$）对应游戏第 $i$ 轮的第 1、2 步。- 参数 $N$ 是第 $i$ 轮第 1 步中给 Azzurro 的卡片上写的整数 $N$。
- 参数 $L$ 是第 $i$ 轮第 1 步中给 Azzurro 的卡片上写的整数 $L_i$。
- 参数 $S$ 是第 $i$ 轮第 1 步中给 Azzurro 的卡片上写的字符串 $S_i$。
对于每次对
Azzurro函数的调用，你的程序必须返回一个 $N \times N$ 的二维数组 $x$，其每个元素均为 $0$ 或 $1$。如果不满足此条件，你的程序将被判定为 Wrong Answer [1]。- 如果 $x[r][c] = 0$（$0 \le r \le N - 1, 0 \le c \le N - 1$），表示单元格 $(r, c)$ 被涂成蓝色。
- 如果 $x[r][c] = 1$（$0 \le r \le N - 1, 0 \le c \le N - 1$），表示单元格 $(r, c)$ 被涂成红色。
第二个文件是 Bordeaux.cpp。它应该实现 Bordeaux 的策略。它应该实现以下函数。程序应使用预处理指令 #include 包含 Bordeaux.h。
std::string Bordeaux(int N, int L, std::vector<std::vector<int>> T)该函数在 Azzurro 完成网格涂色后被调用。该函数总共会被调用 $Q$ 次。第 $i$ 次调用（$1 \le i \le Q$）对应游戏第 $i$ 轮的第 4、5 步。- 参数 $N$ 是第 $i$ 轮第 4 步中给 Bordeaux 的卡片上写的整数 $N$。
- 参数 $L$ 是第 $i$ 轮第 4 步中给 Bordeaux 的卡片上写的整数 $L_i$。
- 参数 $T$ 是第 $i$ 轮第 4 步中给 Bordeaux 的网格对应的 $N \times N$ 二维数组。如果 $T[r][c] = 0$，则单元格 $(r, c)$（$0 \le r \le N - 1, 0 \le c \le N - 1$）为蓝色；如果 $T[r][c] = 1$，则为红色。
对于每次对 Bordeaux 函数的调用，你的程序必须返回一个长度为 $L_i$、由 'A' 和 'B' 组成的字符串 $s$。如果不满足此条件，你的程序将被判定为 Wrong Answer [2]。
重要说明
- 你的程序可以实现其他内部使用的函数，或使用全局变量。提交的文件将与评测程序一起编译，并成为一个单一的可执行文件。所有全局变量和内部函数都应在匿名命名空间中声明，以避免与其他文件冲突。在评测时，它将作为 Azzurro 和 Bordeaux 两个进程执行。Azzurro 进程和 Bordeaux 进程不能共享全局变量。
- 你的程序不得使用标准输入和标准输出。你的程序不得通过任何方式与其他文件通信。但是，你的程序可以将调试信息输出到标准错误。
编译与测试运行
你可以从比赛网页下载包含示例评测程序的压缩包来测试你的程序。压缩包中还包含你程序的示例源文件。
示例评测程序文件名为 grader.cpp。为了测试你的程序，请将 grader.cpp、Azzurro.cpp、Bordeaux.cpp、Azzurro.h、Bordeaux.h 放在同一目录下，并运行以下命令来编译你的程序：
g++ -std=gnu++20 -O2 -o grader grader.cpp Azzurro.cpp Bordeaux.cpp
或者，你可以运行压缩包中包含的 compile.sh。在这种情况下，运行以下命令来编译你的程序：
./compile.sh
编译成功后，将生成可执行文件 grader。
请注意，实际的评测程序与示例评测程序不同。示例评测程序将作为一个单一进程执行，它会从标准输入读取数据并将结果写入标准输出。在实际的评测程序中，Chiaro 选择的路径是预先固定的。也就是说，Chiaro 选择的路径在调用你提交程序中的 Azzurro 和 Bordeaux 函数之前就已经确定了。
样例输入格式
示例评测程序从标准输入读取以下数据：
$Q \ N$ $L_1$ $S_1$ $R_1$ $L_2$ $S_2$ $R_2$ $\vdots$ $L_Q$ $S_Q$ $R_Q$
此处，$R_i$（$1 \le i \le Q$）是一个长度为 $2(N - 1)$ 的字符串，恰好包含 $N - 1$ 个 'D' 和 $N - 1$ 个 'R'。该字符串表示 Chiaro 在第 $i$ 轮选择的路径，该路径从 $(0, 0)$ 开始，通过重复仅向相邻的下方或右方单元格移动，到达 $(N - 1, N - 1)$。具体来说，从 $(0, 0)$ 开始，对于每个 $j = 1, 2, \dots, 2(N - 1)$，如果 $R_i$ 的第 $j$ 个字符是 'D'，则移动到下方相邻的单元格；如果是 'R'，则移动到右方相邻的单元格。重复此过程最终会到达 $(N - 1, N - 1)$。
样例输出格式
示例评测程序将以下信息输出到标准输出（引号仅为清晰起见）：
- 如果你的程序被判定为正确，它会写入 $L^*$ 的值，格式为 “Accepted: 26”。关于 $L^*$ 的值，请参阅“评分”部分。
- 如果你的程序被判定为任何类型的 Wrong Answer，示例评测程序会写入其类型，例如 “Wrong Answer [1]”。
如果你的程序满足多种 Wrong Answer 的条件，示例评测程序仅报告其中一种。当满足其中一个错误答案条件时，示例评测程序可能会终止执行。
数据范围
所有输入数据满足以下条件：
- $1 \le Q \le 30\,000$。
- $N = 8$。
- $1 \le L_i \le 51$（$1 \le i \le Q$）。
- $Q, L_i$（$1 \le i \le Q$）均为整数。
- $S_i$（$1 \le i \le Q$）是长度为 $L_i$、由 'A' 和 'B' 组成的字符串。
- $R_i$（$1 \le i \le Q$）是长度为 $2(N - 1)$、恰好包含 $N - 1$ 个 'D' 和 $N - 1$ 个 'R' 的字符串。
评分
如果你的程序在任何测试用例中被判定为任何类型的 Wrong Answer [1] 或 Wrong Answer [2]（参见“实现细节”）、Time Limit Exceeded、Memory Limit Exceeded 或 Runtime Error，你的得分为 0 分。
否则，令 $L^*$ 为该任务所有测试用例中以下值的最小值。你的得分根据下表计算：
- 满足 Azzurro 和 Bordeaux 在所有满足 $L_i \le L$ 的轮次中获胜的最大 $L$ 值。但是，如果他们在测试用例的所有轮次中都获胜，我们设 $L = 51$。
| $L^*$ 的值 | 得分 |
|---|---|
| $1 \le L^* \le 28$ | $2L^*$ 分 |
| $29 \le L^* \le 39$ | $L^* + 28$ 分 |
| $40 \le L^* \le 50$ | $67 + 3(L^* - 40)$ 分 |
| $L^* = 51$ | $100$ 分 |
样例
| 样例输入 1 | 样例函数调用 |
|---|---|
| 函数调用 | 返回值 |
| 2 2 | Azzurro(2, 1, "B") |
| 1 | [[1, 0], [0, 1]] |
| B | Bordeaux(2, 1, [[0, 1], [0, 0]]) |
| RD | "B" |
| 3 | Azzurro(2, 3, "ABB") |
| ABB | [[0, 0], [0, 0]] |
| DR | Bordeaux(2, 3, [[1, 0], [1, 1]]) |
"ABB" |
此样例输入包含 $Q (= 2)$ 轮，每轮使用一个 $N \times N$ 网格（$N = 2$）。在此示例中，第一轮的流程如下：
- Azzurro 将 $(0, 1)$ 和 $(1, 0)$ 涂成蓝色，将 $(0, 0)$ 和 $(1, 1)$ 涂成红色。然后他将网格交给 Chiaro。
- Chiaro 在 Azzurro 和 Bordeaux 都看不见的情况下执行以下操作： (a) 他选择路径 $(0, 0) \to (0, 1) \to (1, 1)$ 作为从 $(0, 0)$ 到 $(N - 1, N - 1)$ 的路径。 (b) 对于路径上的三个单元格 $(0, 0), (0, 1), (1, 1)$，他改变它们的颜色。结果，$(0, 0), (0, 1), (1, 1)$ 的颜色分别变为蓝色、红色和蓝色。
- Bordeaux 可以通过在纸上写下 “B” 来赢得这一轮。
第二轮的流程如下：
- Azzurro 将所有单元格涂成蓝色。然后他将网格交给 Chiaro。
- Chiaro 在 Azzurro 和 Bordeaux 都看不见的情况下执行以下操作： (a) 他选择路径 $(0, 0) \to (1, 0) \to (1, 1)$ 作为从 $(0, 0)$ 到 $(N - 1, N - 1)$ 的路径。 (b) 对于路径上的三个单元格 $(0, 0), (1, 0), (1, 1)$，他改变它们的颜色。结果，$(0, 0), (1, 0), (1, 1)$ 的颜色全部变为红色。
- Bordeaux 可以通过在纸上写下 “ABB” 来赢得这一轮。
请注意，此样例输入不满足问题的约束条件。可以从比赛网站下载的文件 sample-01-in.txt 对应于样例输入 1。文件 sample-02-in.txt 是一个满足约束条件的样例输入。