这是一个交互式问题。

Hanburmi 有一个长度为 $N$ 的排列 $A$。换句话说，$A$ 是一个序列，其中 $1$ 到 $N$ 的每个整数恰好出现一次。你需要从 Hanburmi 已知的排列 $A$ 中找到索引 $x$，使得 $A_x = \left\lfloor \frac{N}{2} \right\rfloor + 1$。为此，你可以向 Hanburmi 提出最多 $10^4$ 次以下类型的询问。

对于每次询问，你需要选择一个长度为 $N$ 的排列 $p$。Hanburmi 会考虑一个直方图 $H$，其中第 $i$ 个柱状条的高度为 $A_{p_i}$。在所有完全包含在 $H$ 中且底边与直方图底部平行的矩形中，Hanburmi 会找到一个面积最大的矩形。如果存在多个面积最大的矩形，Hanburmi 会选择其中高度最大的一个。如果选定的矩形跨越第 $l$ 个柱状条到第 $r$ 个柱状条，且高度为 $h$，Hanburmi 将返回三个整数 $l$、$r$ 和 $h$。

交互

你的程序应通过标准输入和标准输出与交互器进行交互，格式如下。

首先，给定整数 $N$。

通过打印以下询问，你将在下一行收到三个用空格分隔的整数 $l$、$r$ 和 $h$。此询问最多可以使用 $10^4$ 次。

• ? $p_1$ $p_2$ $\cdots$ $p_N$ （其中 $p$ 是长度为 $N$ 的排列）

你可以通过打印以下询问来提交答案。此询问不计入询问次数，程序在打印后必须立即终止。

• ! $x$ （其中 $1\le x\le N$）

交互器是非自适应的。换句话说，排列 $A$ 在交互开始前就已经固定，并且在交互过程中不会改变。

对于每个测试用例，如果提交的答案正确，你将收到 Accepted；如果答案不正确，你将收到 Wrong Answer。但是，如果你没有在题目规定的限制内通过正确的交互方式打印答案，可能会出现意外结果。

数据范围

• $3\le N\le 50$
• $1\le l\le r\le N$
• $1\le h\le N$

子任务

| :---: | :---: | :---: | | 编号 | 分值 | 数据范围 | | 1 | 15 | $N \le 7$ | | 2 | 85 | 无额外限制 |

样例

输入格式 1

3
1 2 2
1 1 3
1 2 2

输出格式 1

? 1 2 3
? 1 3 2
? 2 1 3
! 2

说明

在样例 1 中，这是一个 $A_1=3, A_2=2, A_3=1$ 的例子。

直方图是由多个沿底部排列的矩形组成的形状。每个矩形的宽度固定为 $1$，但高度可能不同。例如，下图展示了一个由高度分别为 $3, 5, 8, 8, 4$ 和 $7$ 的矩形组成的直方图。

你在打印输出后必须立即刷新缓冲区。你可以使用：

• C --- fflush(stdout)
• C++ --- std::cout.flush()
• Python --- sys.stdout.flush()
• Java --- System.out.flush()
• 其他语言请查阅相关文档。

另外，请注意样例输入和输出中的空行仅为了清晰起见，在实际交互中不会出现。