Description

现存在一个长度为 $n$ 的隐藏排列 $p$。你可以进行如下询问若干次：选择三元组 $(l,r,k)$，满足 $1\leq l\leq r\leq n$，$1\leq k\leq r - l + 1$，交互库会返回下标在 $[l,r]$ 内的第 $k$ 大值。

对于一次询问操作，其代价为 $\frac{1}{r-l+1}$，你需要在不超过 $11.8$ 的代价内得出排列。

交互库不自适应，也就是说，你所需得到的排列在交互开始前就已经确定。

Input Format

输入第一行是一个正整数 $t$ ($1 \le t \le 5$) 表示测试组数。

对于每组数据，输入一行 $n$ ($1 \le n \le 1000$) 表示排列 $p$ 的长度。

当你已经得到排列，你应当输出形如 ! p1 p2 ... pn 表示你得出的排列。

本题使用 IO 交互模式。

交互格式

• ? l r k，询问下标在 $[l,r]$ 内的第 $k$ 大值。

• ! p1 p2 p3 ... pn，输出答案。

请注意：在每组数据中，请保证询问操作的代价总和不超过 $11.8$。

需要注意的是，在每一次操作后，需要调用以下函数刷新缓存：

• 对于 C/C++：fflush(stdout);
• 对于 C++：std::cout << std::flush;
• 对于 Java：System.out.flush();
• 对于 Python：stdout.flush();
• 对于 Pascal：flush(output);

对于其他语言，请自行查阅对应语言的帮助文档。

Output Format

见「交互格式」。

1
5

2

3

1

4

? 1 1 1

? 2 2 1

? 3 3 1

? 4 4 1

! 2 3 1 4 5