这是一个通信任务。请注意，此任务仅允许使用 C++。

Takina 和 Chisato 正在参加一个水果大会。在与他们最喜欢的水果扮演者合影一天后，他们偶然发现了一个游戏摊位。

游戏规则如下： 共有 $n$ 个水果，每个水果都有一个从 $1$ 到 $n$ 的不同标签。 其中恰好有一个水果是柠檬，但 Takina 和 Chisato 目前都不知道是哪一个。 * Takina 将会逐个收到所有 $n$ 个水果。她的目标是将柠檬的标签传达给 Chisato（在此过程中 Chisato 被蒙住双眼）。

在收到任何水果之前，Takina 会得到一个数组 $p$，它代表水果标签出现的顺序。$p[1]$ 将是第一个水果的标签，$p[2]$ 将是第二个水果的标签，依此类推。然后，Takina 将写下一个仅包含 $0$ 和 $1$ 的二进制字符串 $b$。该字符串的长度不得超过 $5000$ 个字符，但可以为空。令 $x$ 表示 $b$ 的长度。

之后，水果会按照上述顺序逐个交给 Takina。在收到每个水果时，Takina 会被告知它是否是柠檬。 如果该水果不是柠檬，Takina 可以选择是否吃掉它。此决定必须在收到下一个水果之前做出，且一旦做出便无法更改。 如果该水果是柠檬，Takina 不得吃掉它。

令 $y$ 表示 Takina 吃掉的水果总数。

最后，Chisato 会收到字符串 $b$ 以及未被吃掉的水果的已排序标签列表。利用这些信息，Chisato 必须确定哪个水果是柠檬。

Takina 和 Chisato 决定玩 $t$ 次这个游戏。请为他们设计一种策略，在正确识别柠檬的同时，最小化 $x$ 和 $y$。

实现细节

这是一个通信任务。不要从标准输入读取数据或向标准输出写入数据。

你需要实现三个过程。

对于 Takina，你应该实现：

std::string init(int subtask, int n, std::vector<int> p)

• subtask：测试用例所属的子任务索引。
• n：水果的数量。
• p：一个长度为 $n + 1$ 的数组，其中：
  • $p[0] = 0$，且
  • 对于每个 $1 \le i \le n$，$p[i]$ 是将要交给 Takina 的第 $i$ 个水果的标签。
• 此过程在每个测试用例中被调用 $t$ 次，即每场游戏开始时调用一次。

此过程应返回字符串 $b$，长度在 $0$ 到 $5000$（含）之间，且仅由 $0$ 和 $1$ 组成。如果返回的字符串长度或格式无效，你将收到 Wrong Answer 判决。

bool receive_fruit(int id, bool is_lemon)

• id：交给 Takina 的水果标签。
• is_lemon：如果给出的水果是柠檬，则为 true，否则为 false。
• 此过程在每场游戏中被调用 $n$ 次，即每个水果调用一次。

此过程应返回 true 表示应该吃掉该水果，否则返回 false。如果在 is_lemon 为 true 时返回 true，你将收到 Wrong Answer 判决。

对于 Chisato，你应该实现：

int answer(int subtask, int n, std::string b, std::vector<int> uneaten)

• subtask：测试用例所属的子任务索引。
• n：水果的数量。
• b：init 返回的字符串。
• uneaten：长度为 $n - y + 1$ 的已排序向量，包含未被 Takina 吃掉的水果标签，其中：
  • uneaten[0] = 0，且
  • uneaten[i] 是未被吃掉的水果中第 $i$ 小的标签。
• 此过程在每场游戏中被调用 $t$ 次，即每场游戏结束时调用一次。

此过程应返回一个整数，即柠檬的标签。如果返回值与正确标签不匹配，你将收到 Wrong Answer 判决。

在实际评测中，调用上述过程的程序会运行两次： 1. 在第一次运行中，执行 $t$ 次以下步骤： 调用一次 init。 按照交给 Takina 的水果顺序调用 $n$ 次 receive_fruit。 你的程序可以在连续的调用中存储并保留信息。 2. 在第二次运行中，游戏的顺序可能与第一次运行不同。对于 $t$ 场游戏中的每一场： 调用一次 answer。除了传递给 answer 的参数外，你的程序不得访问第一次运行中的信息。

由于该过程可能被多次调用，你应该注意之前调用中剩余数据对当前调用的影响。

子任务

对于所有测试用例，输入满足以下限制： $1 \le t \le 10\,000$ $n = 500$ 对于所有 $1 \le i \le n$，$1 \le p[i] \le n$ 恰好有一个柠檬。

对于每个子任务，你的程序将根据 Takina 写入的字符串长度 $x$ 和她吃掉的水果数量 $y$ 进行不同的评分。每个测试用例的得分是根据所有 $t$ 场游戏中的最大 $x$ 值和最大 $y$ 值计算得出的。

样例

考虑一场游戏 ($t = 1$) 且 $n = 4$。注意这不满足输入限制，仅用于演示目的。

假设 Takina 得到的顺序为 $p = [0, 3, 1, 4, 2]$。这意味着水果将按以下标签顺序呈现：$3, 1, 4, 2$。假设标签为 $4$ 的水果是柠檬。

首先，调用 init。Takina 接收参数 subtask、$n$ 和 $p$，并返回字符串 $b$。

然后，对给定的每个水果调用一次 receive_fruit。每次，Takina 都会被告知该水果是否为柠檬，并决定是否吃掉它。

最后，Chisato 收到字符串 $b$ 和未被吃掉的水果的已排序集合，并调用过程 answer。

输入格式 1

(subtask, 4, [0, 3, 1, 4, 2])

输出格式 1

"101"

说明

一种可能的调用序列和返回值如下：

在此示例中，Takina 吃掉了标签为 $3$ 和 $2$ 的水果，因此未被吃掉的水果为 $\{1, 4\}$。传递给 answer 的向量 uneaten 因此为 [0, 1, 4]。

使用 $b$ 和 uneaten，过程 answer 返回 $4$，即柠檬的标签。该策略成功地在 $x = 3$ 和 $y = 2$ 的情况下正确识别了柠檬。

测试

你可以从附件中下载样例评测程序 (grader.cpp)、头文件 (lemon.h) 和解决方案模板 (lemon.cpp)。提供了两个输入文件用于测试：sample1.txt 和 sample2.txt。你可以使用脚本 compile.sh 进行编译，使用 run.sh 运行你的解决方案进行测试。

CMS 用户测试不支持此问题。

样例评测程序

提供了一个样例评测程序以帮助你在本地测试你的实现。与官方评测程序不同，样例评测程序仅运行你的程序一次，且不会改变 Takina 和 Chisato 的测试顺序。

输入格式

第一行包含一个整数 subtask。 第二行包含一个整数 $t$。 接下来的 $t$ 行输入每行描述一场游戏。每场游戏描述如下： 一行包含两个空格分隔的整数 $n$ 和 $l$，分别代表水果数量和柠檬的标签。 一行包含 $n$ 个空格分隔的整数 $p[1], p[2], \dots, p[n]$。

subtask
t
n_1 l_1
p_1[1] p_1[2] ... p_1[n_1]
n_2 l_2
p_2[1] p_2[2] ... p_2[n_2]
...
n_t l_t
p_t[1] p_t[2] ... p_t[n_t]

输出格式

样例评测程序输出一个实数，表示根据所有游戏中的 $x$ 和 $y$ 值计算出的得分比例。

说明

额外的诊断信息可能会打印到标准错误。样例评测程序不模拟官方评测程序的行为。