题目背景

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

题目描述

Anna 和 Bruno 是赌术大师。他们将和担任庄家的 D-taro 玩一个游戏。在这个游戏中，Anna 和 Bruno 分别待在不同的房间里。他们只能使用一台损坏的装置相互通信。D-taro 会给 Anna 一个整数。对于 Anna 和 Bruno 来说，这个游戏的目标是使用该装置，把给定的整数从 Anna 传递给 Bruno。

当游戏开始时，一开始，Anna 声明一个整数 $m$，其取值在 1 到 2 000（含）之间。然后他们进行 $Q$ 轮。第 $i$ 轮（$1 \le i \le Q$）按如下方式进行。

1. D-taro 给 Anna 一个整数 $A_i$。
2. Anna 向装置输入数组 $s_i, t_i$。数组 $s_i, t_i$ 的每个元素都必须为 0 或 1。数组 $s_i, t_i$ 的长度必须相同，且长度在 1 到 $m$（含）之间。
3. 令 $u_i$ 为由数组 $s_i$ 和 $t_i$ 通过 riffle shuffle（见下文）得到的数组。然后装置将 $u_i$ 发送给 Bruno。
4. Bruno 向 D-taro 发送一个整数。若该整数与 D-taro 给 Anna 的整数 $A_i$ 相同，则 Anna 和 Bruno 在本轮获胜。

请编写实现 Anna 和 Bruno 策略的程序，使他们在全部 $Q$ 轮中都能获胜。

洗牌交错（riffle shuffle）

若能将数组 $Z$ 的元素划分为两组，并满足以下两个条件，则称数组 $Z$ 是由数组 $X$ 和数组 $Y$ 通过 riffle shuffle 得到的。

• 由第一组元素按原有顺序组成的数组等于数组 $X$。
• 由第二组元素按原有顺序组成的数组等于数组 $Y$。

例如，数组 $Z = [1, 1, 1, 0, 0, 0]$ 可由 $X = [1, 1, 0]$ 与 $Y = [1, 0, 0]$ 通过 riffle shuffle 得到，因为由 $Z$ 的第 1、2、4 个元素按原顺序组成的数组为 $[1, 1, 0]$，而由第 3、5、6 个元素按原顺序组成的数组为 $[1, 0, 0]$。

另一方面，若 $X = [1, 1, 0]$、$Y = [1, 0, 0]$，而 $Z = [0, 0, 0, 1, 1, 1]$，则数组 $Z$ 不是由 $X$ 和 $Y$ 通过 riffle shuffle 得到的。

实现细节

你需要提交两个文件。

第一个文件是 Anna.cpp。它应实现 Anna 的策略，并实现下列函数。程序应通过预处理指令 #include 包含 Anna.h。

• int Declare()

  该函数在开始时被调用一次。

  • 返回值是 Anna 声明的整数 $m$。
  • 整数 $m$ 必须在 1 到 2 000（含）之间。若不满足此条件，你的程序将被判为 Wrong Answer [1]。

• std::pair<std::vector<int>, std::vector<int>> Anna(long long A)

  在调用 Declare 之后，该函数将被调用 $Q$ 次。第 $i$ 次调用（$1 \le i \le Q$）对应第 $i$ 轮的步骤 1 和步骤 2。

  • 参数 $A$ 是 D-taro 给 Anna 的整数 $A_i$。
  • 返回值是 Anna 输入到装置中的两个数组 $s_i, t_i$ 组成的二元组。
  • 数组 $s_i, t_i$ 的每个元素都必须为 0 或 1。若不满足此条件，你的程序将被判为 Wrong Answer [2]。
  • 数组 $s_i, t_i$ 的长度都必须在 1 到 $m$（含）之间。若不满足此条件，你的程序将被判为 Wrong Answer [3]。
  • 数组 $s_i, t_i$ 的长度必须相同。若不满足此条件，你的程序将被判为 Wrong Answer [4]。

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

• long long Bruno(std::vector<int> u)

  在 Anna 向装置输入数组之后，该函数会被调用一次。总共，该函数会被调用 $Q$ 次。第 $i$ 次调用（$1 \le i \le Q$）对应第 $i$ 轮的步骤 3 和步骤 4。

  • 参数 u 是装置在第 $i$ 轮发送给 Bruno 的数组 $u_i$。
  • 返回值是 Bruno 发送给 D-taro 的整数。
  • 返回值必须与 D-taro 给 Anna 的整数 $A_i$ 相同。若不满足此条件，你的程序将被判为 Wrong Answer [5]。

重要注意事项

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

编译与本地测试

你可以从竞赛网页下载一个压缩包，其中包含用于本地测试你程序的样例评测器。压缩包还包含你程序的样例源代码。

样例评测器为文件 grader.cpp。为了测试你的程序，请将 grader.cpp、Anna.cpp、Bruno.cpp、Anna.h、Bruno.h 放在同一目录下，并运行如下命令以编译程序。

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

编译成功后，会生成名为 grader 的可执行文件。

请注意，实际评测器与样例评测器不同。样例评测器以单进程形式运行，从标准输入读入数据，并将结果写到标准输出。

输入格式

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

$Q$
$A_1$
$A_2$
$\vdots$
$A_Q$

输出格式

样例评测器向标准输出写出如下信息（引号仅为说明）。

• 若你的程序被判定为正确，它会输出函数 Declare 的返回值 $m$，例如 “Accepted: 2000”。
• 若你的程序被判定为任一类 Wrong Answer，样例评测器会写出其类型，例如 “Wrong Answer [1]”。

如果你的程序同时触犯多类 Wrong Answer 的条件，样例评测器只报告其中一种。

样例评测器在每一轮计算 riffle shuffle 时使用伪随机数。其结果在不同执行中不会改变。为了更改伪随机数的种子，请如下方式执行样例评测器。

./grader 2022

第一个参数应为一个整数。

提示

约束

• $1 \le Q \le 1\,000$。
• $1 \le A_i \le 1\,000\,000\,000\,000\,000\,000 \ (= 10^{18}) \ (1 \le i \le Q)$。

子任务

1. （5 分）$A_i \le 2\,000 \ (1 \le i \le Q)$。
2. （5 分）$A_i \le 4\,000\,000 \ (1 \le i \le Q)$。
3. （3 分）$A_i \le 10\,000\,000 \ (= 10^7) \ (1 \le i \le Q)$。
4. （12 分）$A_i \le 100\,000\,000 \ (= 10^8) \ (1 \le i \le Q)$。
5. （15 分）$A_i \le 100\,000\,000\,000 \ (= 10^{11}) \ (1 \le i \le Q)$。
6. （60 分）无限制。对于本子任务，你的得分计算如下。
   • 令 $m^*$ 为本子任务所有测试中，Anna 声明的整数 $m$ 的最大值。
   • 你的得分如下所示。

$m^*$ 的取值	分数
$201 \le m^* \le 2\,000$	$40 - 25 \times \log_{10}\!\left(\dfrac{m^*}{200}\right)$ 分（向下取整为整数）
$161 \le m^* \le 200$	40 分
$156 \le m^* \le 160$	44 分
$151 \le m^* \le 155$	48 分
$146 \le m^* \le 150$	52 分
$141 \le m^* \le 145$	56 分
$m^* \le 140$	60 分

样例通信

下面给出样例评测器的一个样例输入以及相应的函数调用。

样例输入 1

2
42
2000

调用	返回值
Declare()	4
Anna(42)	([0, 0, 1, 0], [1, 1, 0, 1])
Bruno([1, 0, 0, 1, 0, 1, 0, 1])	42
Anna(2000)	([0, 1], [0, 0])
Bruno([0, 0, 1, 0])	2000

在该样例输入中，共有 $Q \ (= 2)$ 轮。对于第 1 轮，D-taro 给 Anna 的整数为 $A_1 \ (= 42)$。

对于第 2 轮，D-taro 给 Anna 的整数为 $A_2 \ (= 2000)$。

该样例输入满足所有子任务的约束。