本题为交互题。

在甜品节即将开幕的前夕，主厨正在精心雕琢店里的招牌名作——“千层幻彩慕斯”。这道甜品由 $n$ 块风味各异的慕斯组合而成，编号依次为 $0,1,\dots,n-1$。

然而在慌乱之中，助手不小心混淆了慕斯的摆放次序。如今它们从左到右一字排开，形成了一个未知的位置排列 $p=(p_0,p_1,\dots,p_{n-1})$，其中 $p_i$ 代表第 $i$ 个位置上放置的慕斯编号。

为了厘清每块慕斯的准确位置，你可以借助甜品测试仪进行检测。每次选定三个互不相同的位置 $x,y,z$，测试仪便能反馈这三块慕斯中最小与最大编号之和：

$$ \min(p_x,p_y,p_z)+\max(p_x,p_y,p_z). $$

开幕钟声即将敲响，你能否通过有限次的检测，准确还原出每一块慕斯的真实位置？

有一个长度为 $n$ 的排列 $p$，其元素恰好为 $0,1,\ldots,n-1$。你不知道 $p$ 的具体内容。

你可以选取三个互不相同的下标 $x,y,z$，交互库会返回

$$ \min(p_x,p_y,p_z)+\max(p_x,p_y,p_z). $$

你的任务是还原整个排列。询问次数上限和根据询问次数计算分数的方式见下文。

实现细节

选手不需要，也不应该实现 main 函数。提交的源文件应包含：

#include "mousse.h"

你需要实现以下两个函数：

void init(int c);
std::vector<int> mousse(int c, int n);

• $c$ 为子任务编号；$c=0$ 表示样例。每个测试点恰好包含一组数据。交互库对该测试点调用一次 init(c)，随后调用一次 mousse(c,n)。
• mousse 应返回长度为 $n$ 的数组，其中第 $i$ 个元素为 $p_i$，下标从 $0$ 开始。

选手可以调用以下函数进行一次询问：

int query(int x, int y, int z);

必须满足 $0\le x,y,z < n$，且 $x,y,z$ 两两不同。函数返回 $\min(p_x,p_y,p_z)+\max(p_x,p_y,p_z)$。

测试程序方式

附件包含 mousse.h、本地交互库 grader.cpp 和示例程序 template_mousse.cpp。将自己的程序保存为 mousse.cpp，可以在本题目录下运行：

g++ grader.cpp mousse.cpp -o mousse -O2 -std=c++14
./mousse < mousse1.in

本地交互库从标准输入读入隐藏排列，选手程序不得自行读取这些数据。输入格式如下：

• 第一行两个整数 $c,n$。
• 第二行输入 $p_0,p_1,\ldots,p_{n-1}$。

如果答案正确，交互库输出 Correct! 和 Max queries used: Q，其中 $Q$ 是该测试点的询问次数；如果答案错误，输出 Wrong answer.。传入非法询问或超出询问次数上限时，程序向标准错误流输出错误信息并退出。可以添加 -v 参数查看该测试点的询问次数。

样例

input

0 10
0 2 9 1 5 8 3 7 6 4

output

Correct!
Max queries used: 15

explanation

例如调用 query(0,1,2) 时，三个对应数值为 $0,2,9$，返回 $0+9=9$。参考程序在这组数据中使用 $15$ 次询问。你使用其他策略时，这个次数可以不同。

数据范围

对于所有测试数据，$n\in\{10,100,10^5\}$，$p$ 为 $0\sim n-1$ 的排列。每个测试点恰好包含一组数据。

样例的 $c=0$、$n=10$，询问上限为 $1000$。

评分方式

注意：

• 交互库不是适应性的。每个测试点的排列在调用选手程序前已经确定，不会随询问改变。
• 选手不得通过读取标准输入或其他非法方式获取隐藏排列。最终评测使用的交互库与本地交互库的实现可能不同。

若某测试点中 mousse 返回错误答案、query 的参数不合法，或询问次数超过该子任务的 $Q_{\max}$，该测试点的得分倍率为 $0$。

子任务 $1,2$ 中，只有全部测试点正确才能获得该子任务的全部分数。

对于子任务 $3,4$，若任一测试点的得分倍率为 $0$，该子任务得 $0$ 分。否则，令 $Q$ 为该子任务所有测试点中的最大询问次数，得分倍率 $f(Q)$ 由下表确定：

若 $Q\le 99970$，则 $f(Q)=100\%$。若 $Q$ 位于表中相邻两行 $(Q_i,f_i)$ 与 $(Q_{i+1},f_{i+1})$ 之间，则有：

$$ f(Q)=f_i+\frac{Q-Q_i}{Q_{i+1}-Q_i}(f_{i+1}-f_i). $$

子任务 $3$ 的得分为 $30f(Q)$，子任务 $4$ 的得分为 $60f(Q)$。最终得分按小数点后 $3$ 位四舍五入。

时间限制：$10\ \mathrm{s}$。

空间限制：$512\ \mathrm{MiB}$。