题目描述

hhz 有一个 $1$ 到 $n$ 的排列，你需要猜出它。

你只能问 hhz 以下两个问题：

1. 给定不同的两个数 $i,j$，hhz 会告诉你 $a_i$ 和 $a_j$ 的大小关系。
2. 给定两两不同的 $i,j,k$，hhz 会告诉你 $a_i,a_j,a_k$ 的中位数。

你只能进行 $2$ 次询问 $1$ 和 $m$ 次询问 $2$，你需要猜出这个排列。

任务

这是一道交互题。

你必须包含头文件 guess.h。

你需要实现如下函数：

vector<int> solve(int n, int m);

这个函数只会被调用一次。你需要返回一个长为 $n$ 的数组表示排列。

你可以调用如下过程：

bool query1(int i, int j);

若 $a_i\lt a_j$ 这个函数返回 $1$，否则返回 $0$。

你需要保证 $0\leq i,j\lt n$，$i\neq j$。

int query2(int i, int j, int k);

这个函数返回 $a_i,a_j,a_l$ 的中位数。

你需要保证 $0\leq i,j,k\lt n$，$i\neq j$，$j\neq k$，$k\neq i$。

样例交互库

样例交互库以如下格式读入数据：

第一行两个整数 $n, m$。

第二行 $n$ 个整数表示排列。

如果你的交互过程合法且返回排列正确，样例交互库会输出 Accepted cnt=... 表示你使用操作 $2$ 的次数，否则会输出 Wrong Answer [id]，你可以查阅交互库以获得具体错误信息。

数据范围与提示

本题捆绑测试。

对于所有数据，$50\leq n\leq 5\cdot 10^5$，$2n\leq m\leq 10^6$。

交互库自适应。

时间限制：$2\texttt{s}$

空间限制：$512\texttt{MB}$

Hacks

你可以通过以下格式来提交 Hack：

• $seed$
• $n$ $m$ $mode$ $arg_1$ $arg_2$ $\cdots$ $arg_k$

其中各个参数的含义如下：

• $seed$：用于随机的种子，其需满足 $0 \leq seed < 2^{31} = 2\,147\,483\,648$。
• $n$：即题意中的 $n$。其需满足 $50 \leq n \leq 5 \cdot 10^5$。
• $m$：即题意中的 $m$。其需满足 $2n\leq m\leq 10^6$。
• $mode$：交互库所使用的策略。你需要满足 $0 \leq mode \leq 3$：
  • 当 $mode = 0$ 时：
    • 交互库将随机一个排列作为 $a$。
    • 参数个数 $k=0$，即对应的输入的第二行只有三个整数。
  • 当 $mode = 1$ 时：
    • 交互库 adaptive，将根据选手的询问动态构造 $a$。
    • 参数个数 $k=1$，其包含恰好一个参数 $init\_num$，其需满足 $0 \leq init\_num < n$。即对应的输入的第二行只有四个整数。
  • 当 $mode = 2$ 时：
    • 交互库 adaptive，将根据选手的询问动态构造 $a$。
    • 参数个数 $k=1$，其包含恰好一个参数 $rev$，其需满足 $0 \leq rev \leq 1$。即对应的输入的第二行只有四个整数。
  • 当 $mode = 3$ 时：
    • 将使用你输入的排列作为 $a$。
    • 参数个数 $k=n$，其包含 $n$ 个参数 $a_1,a_2,\cdots,a_n$，满足排列 $a$。即对应的输入的第二行只有 $n+3$ 个整数。

建议在使用 Hack 时，总是使用 $mode = 3$。下面是四组合法的输入数据供你参考：

123456
50 1000000 0

234567
50 1000000 1 1

123123
50 1000000 2 0

67812345
50 1000000 3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50