这是一道交互题。仅支持使用 C++ 语言（版本不低于 C++14）提交。

题目描述

希望市是一座建在浮空岛上面的城市。在浮空岛的边缘，等距离分布着 $n$ 个灯座，围成一个环形。每个灯座上标有 $1\sim n$ 之间的编号，并且按照顺时针方向形成一个长度为 $n$ 的排列 $p_1, p_2, \dots, p_n$。你不知道这个排列，希望通过与系统交互将其还原出来。

你可以使用系统提供的调度功能，每次向一个灯座投入一个灯芯，从而切换该灯座的状态（如果原来未点亮，则点亮；如果原来点亮，则熄灭）。

系统内部会维护一个当前点亮的灯座集合 $S$（最初为空），你无法直接看到集合的内容，但可以通过交互获取如下信息：

你可以一次性提交一组操作（即一系列灯芯投入的目标编号），系统会逐个处理这些操作：

• 如果某个灯座不在 $S$ 中，投入灯芯后它会被点亮（加入 $S$）；
• 如果某个灯座已经在 $S$ 中，投入灯芯会熄灭它（从 $S$ 中移除）；
• 每次操作后，系统会记录当前集合 $S$ 中是否存在一对在环上相邻的灯座，并将所有操作的记录一起返回。

在你一次性提交一组操作并得到了返回的记录以后，$S$ 并不会被清空，而是继续作为下一组操作的初始集合。

实现细节

选手不需要，也不应该实现 main 函数。

选手应确保提交的程序包含头文件 perm.h，可在程序开头加入以下代码实现：

#include "perm.h"

选手需要实现以下函数：

std::vector<int> solve(int n, int subtask);

• 返回一个 vector 表示灯座编号的排列 $p_1\sim p_n$。
• 由于环是没有起点和方向的，因此你回答 $p_1\sim p_n$ 或者 $p_n\sim p_1$ 的任意一个循环移位都算对。

选手可以通过调用以下函数向交互库发送一个批次的询问：

std::vector<bool> query(const std::vector<int>& idx);

• 交互库将维护一个集合 $S$，初始为上一个批次操作完的结果（也就是不重置），依次扫描 idx 中的每个元素 $u$：
  • 如果扫到 $u$ 时 $u\not\in S$，进行一个点亮 $u$ 的操作，使得 $u\in S$；
  • 如果扫到 $u$ 时 $u\in S$，进行一个熄灭 $u$ 的操作，使得 $u\not\in S$；
• 最后返回一个 vector<bool>，依次表示每个操作之后，$S$ 中是否存在相邻的点对。
• 你调用 query 的总次数不可以超过 $10^7$，你每次调用 query 的操作个数之和不可以超过 $3\times10^8$。
• 为了防止 vector 过大产生的意外行为，你还需要保证单次调用 query 的操作个数总是不超过 $10^7$。

测试程序方式

试题目录下的 grader.cpp 是提供的交互库参考实现，最终测试所用的交互库与该参考实现有所不同，因此选手的解法不应该依赖交互库实现。

选手可以在本题目录下使用如下命令编译得到可执行程序：

g++ -static -std=c++14 -O2 -o perm perm.cpp grader.cpp

对于编译得到的可执行程序：

• 可执行文件将从标准输入读入以下格式的数据：
  • 输入的第一行包含两个整数 $\text{subtask},n$，表示子任务编号和环的长度；
  • 输入的第二行包含 $n$ 个整数 $p_1\sim p_n$，按照顺时针方向依次表示 $n$ 个灯座的编号。
• 对于每组数据，交互库将调用一次函数 solve 进行测试，测试全部完成后，交互库将会输出以下信息：
  • 第一行包含你的得分信息；
  • 第二行包含交互库关于测试结果给出的描述。

若你的程序运行结果正确，则交互库会在第二行输出 Correct answers (cnt_round = xxx, cnt_query = xxx)。

否则，交互库会在第二行输出 Wrong answer [x]，其中 x 是 $1\sim5$ 的数字，分别对应以下错误类型：

1. 单次 query 的操作个数超过上限。
2. 所有 query 的总次数超过上限。
3. 所有 query 的总操作个数之和超过上限。
4. 传入 query 的操作不合法。
5. 答案错误。

交互示例

假设 $n = 4$，灯座编号的排列为 $[2,4,1,3]$，下面是一个合法的交互过程：

题目附件说明

本题附件中包含：

1. grader.cpp 是提供的交互库参考实现。
2. perm.h 是头文件，选手不用关心具体内容。
3. perm.cpp 是提供的示例代码，选手可在此代码的基础上实现。
4. perm1.in 和 perm2.in 是大样例，分别对应两个子任务。

子任务

子任务 $1$（$10$ 分）：保证 $n=1000$。

子任务 $2$（$90$ 分）：保证 $n=10^5$。

对于一个测试点，如果你的交互过程不合法，或者返回的答案错误，将会直接获得 $0$ 分。

否则，记你调用 query 的总次数为 $t$，记你每次调用 query 的操作个数之和为 $Q$。

你的得分比例 $\lambda$ 将按照如下公式计算： $$ \lambda=\max\left(0,1-0.1\left(f\left(\dfrac{t}{18}\right)+f\left(\dfrac{Q}{1.5\times10^7}\right)\right)\right) $$ 其中 $$ f(x)=\min\Big(\max\Big(\log_2x,0\Big),8\Big) $$ 然后，如果这个测试点所在的子任务满分为 $S$ 分，那么你将获得 $\lambda\cdot S$ 分。

一个子任务的得分为其中所有测试点得分的最小值，得分向下取整保留两位小数。

保证每个子任务恰有 $10$ 个测试点。保证交互库不是 adaptive 的，也就是说，答案排列是在交互开始前确定好的，不会随着你的询问发生改变。同时，我们还保证答案排列是在所有 $1\sim n$ 的排列中等概率随机选取的。

本题没有 hack 数据。赛后我们会删除所有的 ex_tests 重测，进入主题库后也不允许提交 hack。

题目保证在规定的 query 使用次数限制下，交互库运行所需的时间不超过 $5\texttt{s}$；交互库使用的内存大小固定，且不超过 $64\texttt{MB}$。

提示

注意：选手不应通过非法方式获取交互库的内部信息，如试图直接读取 $p_1\sim p_n$ 的值，或直接与标准输入、输出流进行交互。此类行为将被视为作弊。

本题首先会受到和传统题相同的限制，例如编译错误会导致整道题目得 $0$ 分，运行时错误、超过时间限制、超过空间限制都会导致相应测试点得 $0$ 分。选手只能在程序中访问自己定义的和交互库给出的变量或数据，及其相应的内存空间。尝试访问其他位置空间将可能导致编译错误或运行错误。

时间限制：$10\texttt{s}$（交互库至多使用 $5\texttt{s}$）

空间限制：$1\texttt{GB}$（交互库至多使用 $64\texttt{MB}$）