注意事项

本题为 标准输入输出交互题，目前支持 C++17 及以上提交。

选手需要提交一个完整程序：

• 需要编写 main 函数；
• 从标准输入读取交互器给出的指令；
• 通过标准输出向交互器提交表格或解码结果；
• 每次输出后都必须刷新输出缓冲区；
• 不需要包含任何专用头文件。

本题不是函数接口题，请不要提交只包含 Azzurro / Bordeaux 函数、没有 main 函数的代码。

C++ 中可以使用 endl 自动刷新，也可以手动调用 cout.flush()。

题目背景

Azzurro 和 Bordeaux 是一对来到意大利赌场游玩的搭档。他们决定玩庄家 Chiaro 设计的一个通信游戏。

游戏中，Azzurro 会得到一个只由字符 A 和 B 组成的字符串，他需要通过一张二维表格把这个字符串传递给 Bordeaux。表格是一个 $N\times N$ 的正方形，行和列均从 $0$ 到 $N-1$ 编号，位于第 $r$ 行第 $c$ 列的格子记为 $(r,c)$。

为了防止他们直接交流，Azzurro 和 Bordeaux 被安排在两个不同的房间中。游戏会进行 $T$ 轮。

第 $i$ 轮游戏过程如下：

1. Azzurro 得到一个整数 $L_i$ 和一个长度恰好为 $L_i$ 的字符串 $S_i$。字符串中每个字符都是 A 或 B。Azzurro 还会得到一张初始全为 $0$ 的 $N\times N$ 表格。他可以把其中若干个格子改成 $1$，然后把整张表格交给 Chiaro。
2. Chiaro 收到 Azzurro 填好的表格后，会选择一条从 $(0,0)$ 到 $(N-1,N-1)$ 的路径。这条路径每一步只能向右或向下移动。对于路径经过的每一个格子，Chiaro 都会把其中的值翻转：$0$ 变成 $1$，$1$ 变成 $0$。
3. Bordeaux 得到被 Chiaro 修改后的表格，以及同一个整数 $L_i$。他需要恢复 Azzurro 原本想传递的字符串 $S_i$。

在游戏开始前，Azzurro 和 Bordeaux 知道 Chiaro 会试图破坏通信。他们可以事先商量一套策略，使得尽可能长的字符串都能在任意路径破坏后被正确恢复。

你的任务是编写一个程序，同时扮演 Azzurro 和 Bordeaux。

交互方式

交互器一开始会向你的程序输入两个整数：

T N

其中：

• $T$ 表示游戏轮数；
• $N$ 表示表格大小，本题正式数据中始终有 $N=8$。

随后交互器会依次给出若干条指令。

Azzurro 阶段

当交互器输入：

AZZURRO L S

表示当前轮需要 Azzurro 编码长度为 $L$ 的字符串 $S$。

你的程序需要输出一个 $N\times N$ 的 $0/1$ 表格，表示 Azzurro 交给 Chiaro 的表格。例如可以输出 $N$ 行，每行 $N$ 个整数：

a_{0,0} a_{0,1} ... a_{0,N-1}
a_{1,0} a_{1,1} ... a_{1,N-1}
...
a_{N-1,0} a_{N-1,1} ... a_{N-1,N-1}

所有 $a_{r,c}$ 必须为 0 或 1。

输出完整表格后，必须刷新输出缓冲区。

Bordeaux 阶段

交互器收到表格后，会按照本轮测试数据中预先固定的一条合法路径翻转表格。随后交互器输入：

BORDEAUX L

接着输入 $N$ 行，每行 $N$ 个整数，表示 Chiaro 修改后的表格。

你的程序需要输出一个长度为 $L$ 的字符串，表示 Bordeaux 恢复出的原字符串。该字符串只能包含 A 和 B。

输出后，必须刷新输出缓冲区。

结束指令

所有轮次结束后，交互器会输入：

END

此时你的程序应正常结束。

刷新输出

每次输出表格或字符串后，都必须刷新输出缓冲区。例如：

cout << ans << endl;

或者：

cout << ans << '\n';
cout.flush();

如果没有及时刷新，程序可能会因为交互器收不到输出而超时。

请不要输出除表格和恢复字符串以外的任何多余内容，否则可能导致评测失败。

限制条件

对于所有测试数据，满足：

• $1\le T\le 30000$；
• $N=8$；
• 对每一轮游戏，$1\le L_i\le 51$；
• $S_i$ 只包含字符 A 和 B；
• Chiaro 选择的路径从 $(0,0)$ 到 $(N-1,N-1)$，每一步只向右或向下；
• 交互器不是自适应的，每一轮的字符串和路径在交互开始前已经固定。

判错条件

出现以下情况之一时，该测试点得 $0$ 分：

• Azzurro 阶段输出的表格不是 $N\times N$ 个整数；
• 表格中存在不是 0 或 1 的值；
• Bordeaux 阶段输出的字符串长度不是 $L$；
• 输出字符串中存在不是 A / B 的字符；
• 程序运行错误、超时、超内存；
• 输出了破坏交互协议的多余内容。

评分方式

对于每个测试点，定义 $L^*$ 为满足以下条件的最大整数：

该测试点中所有长度 $L\le L^*$ 的游戏，Bordeaux 都能正确恢复字符串。

如果该测试点中所有游戏都成功，则令 $L^*=51$。

单个测试点的得分由下表决定：

条件	得分
$0\le L^*\le 28$	$2L^*$
$29\le L^*\le 39$	$L^*+28$
$40\le L^*\le 50$	$67+3(L^*-40)$
$L^*=51$	$100$

整题得分取所有测试点得分的最小值。

样例交互说明

下面只是说明交互协议，不代表正式数据规模。

假设交互器一开始输入：

2 2

之后输入：

AZZURRO 1 B

若你的程序输出表格：

1 0
0 1

并刷新输出，交互器会根据本轮隐藏路径翻转若干格子，然后可能输入：

BORDEAUX 1
0 1
0 0

此时你的程序应输出：

B

之后交互器继续下一轮，或者最终输入：

END

提交说明

在 Hydro OJ 中，本题使用标准输入输出交互协议。你需要提交完整程序，不需要包含官方头文件。

建议把编码和解码分别写成两个函数，例如：

vector<vector<int>> encode(int N, int L, string S);
string decode(int N, int L, vector<vector<int>> T);

然后在 main 中按照 AZZURRO / BORDEAUX 指令调用对应函数。

@下发文件