这是一道通信题。

Anna 和 Bruno 是赌博大师。他们将与游戏经销商 D-taro 玩一局游戏。

在这个游戏中，Anna 和 Bruno 住在不同的房间，他们只能使用一台损坏的通信设备。D-taro 会给 Anna 一个整数， 而游戏的目标就是 Anna 将这个整数发送给 Bruno。

游戏开始时，Anna 声明了一个在 $1$ 到 $2000$ 之间的整数 $m$，接下来他们玩 $Q$ 轮游戏。第 $i$ 轮游戏的过程如下：

1. D-taro 向 Anna 给出一个整数 $A_i$。
2. Anna 向通信设备输入两个数组 $s_i,t_i$，数组的每个元素 $s_i,t_i$ 应当是 $0$ 或 $1$，并且两者的长度相同且均为某个 $1$ 到 $m$ 之间的整数。
3. 令 $u_i$ 为 $s_i$ 和 $t_i$ 经过乱序归并得到的结果，通信设备会向 Bruno 发送 $u_i$。
4. Bruno 告诉 D-taro 一个整数，如果这个整数和 $A_i$ 相同，Anna 和 Bruno 在这轮获胜。

以下是乱序归并的定义：

我们称数组 $Z$ 是数组 $X$ 和数组 $Y$ 经过乱序归并得到的结果当且仅当：存在一种划分方式，将 $Z$ 中的元素划成两个集合，满足：

• 第一个集合中的元素按在 $Z$ 中的位置顺次连接得到的数组是 $X$。
• 第二个集合中的元素按在 $Z$ 中的位置顺次连接得到的数组是 $Y$。

例如：数组 $[\underset{―}{1},\underset{―}{1},1,0,0,\underset{―}{0}]$ 可以由数组 $[1,1,0]$ 和数组 $[1,0,0]$ 乱序归并得到。

请你编写两个程序，实现 Anna 和 Bruno 的策略。

任务

本题仅支持符合 C++11 及以上标准的 C++ 语言。

你需要提交两份源文件，分别名为 Anna.cpp 和 Bruno.cpp。

Anna

你必须引用 Anna.h。

这份代码需要实现 Anna 的策略，因此你需要实现如下过程：

int Declare();

这个函数会在每个测试点评测开始时被调用一次。

• 函数的返回值是 Anna 声明的 $m$。
• $m$ 必须是 $1$ 到 $2000$ 之间的整数，否则程序将被判为 Wrong Answer [1]。

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

在 Declare 被调用后，这个函数会被调用 $Q$ 次。第 $i$ 次调用对应第 $i$ 轮游戏的前两轮之间。

• 参数 $\mathtt{\text{A}}$ 表示 D-taro 向 Anna 给出的整数。
• 这个函数的返回值应当是两个数组 $s_i,t_i$，即 Anna 向通信设备输入的字符串。
• $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

你必须引用 Bruno.h。

这份代码需要实现 Bruno 的策略，因此你需要实现如下过程：

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

每当 Anna 将数组对输入设备，调用该函数一次，因此这个函数的第 $i$ 次调用对应游戏第 $i$ 轮的第 $3$ 步和第 $4$ 步之间的过程。

• 参数 $\mathtt{\text{u}}$ 是第 $i$ 轮中，Bruno 接收到的字符串 $u_i$。
• 返回值是 Bruno 向 D-taro 给出的数。
• 返回值应当与 D-taro 向 Anna 给出的相同，否则你的程序将被判为 Wrong Answer [5]。

样例评测库

见附件下载中的 grader.cpp。

你可以通过如下命令编译样例交互库：

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

样例输入格式

第一行一个整数 $Q$。

接下来 $Q$ 行每行一个整数 $A_i$。

样例输出格式

如果你的程序正确运行，样例交互库将会输出形如 Accepted: m 的信息，其中 $m$ 为 Declare 的返回值。

否则会输出形如 Wrong Answer [x] 的信息返回错误编号。

提示

样例评测库的乱序归并是使用伪随机数完成的，这意味着重复允许程序，乱序归并的方式是相同的。你可以通过添加运行参数来改变伪随机数种子，例如：

./grader 2022

样例

input

2
42
2000

explanation

在这组样例，进行了 $Q(=2)$ 轮游戏。

这组样例满足所有测试点的限制。

数据范围与评分方式

• $1\le Q\le 1000$
• $1\le A_i\le {10}^{18}$

Subtasks

1. $\text{(5 points) }{A}_i\le 2000$
2. $\text{(5 points) }{A}_i\le 4\times {10}^6$
3. $\text{(3 points) }{A}_i\le {10}^7$
4. $\text{(12 points) }{A}_i\le {10}^8$
5. $\text{(15 points) }{A}_i\le {10}^{11}$
6. $\text{(60 points)}$ 无特殊限制，评分方式如下：

这个子任务的得分是所有测试点得分的最小值。

对于某个测试点，他的得分由 $m$ 决定，如下表：

保证得分的交互过程中，交互库分别不会使用超过 $\mathtt{\text{0.5s}}$ 时间和 $\mathtt{\text{32MB}}$ 空间。

hack

本题的评测库逻辑与样例库相同。

如果有感兴趣的同学实现或得到了更强的评测库，欢迎与 uoj 管理员联系。

不过这题还是支持更强的 hack 方式的，具体 hack 方法如下：

hack 输入格式

第一行一个整数 $Q$。

接下来每一行开头一个整数 $X$：

• 若 $X>0$，表示 $A=X$，且这组询问由交互库自动乱序归并。
• 若 $X<0$，表示 $A=-X$，接下来输入一个长度在 $2$ 到 $280$ 之间的 01 串，表示乱序归并的方式。

具体的：将 Anna 返回的数组对记作 $s,t$，并且 $s$ 的字典序不大于 $t$，则输入串中，0 所在位置对应某个划分产生的 $s$，1 所在位置对应 $t$。因此，你给出的串还需要保证 01 个数相同。注意，如果 $s,t$ 的长度和不为 01 串的长度，交互库会自动乱序归并。

例如：设 $s=[0,1,0,0],t=[1,0,0,1]$，给出的 01 串为 00101110，则乱序归并的结果为 $[\underset{―}{0},\underset{―}{1},1,\underset{―}{0},0,0,1,\underset{―}{0}]$。

时间限制：两份程序分别 $\mathtt{\text{2s}}$

空间限制：两份程序分别 $\mathtt{\text{512MB}}$