题目背景

再演 - Akali / 音街ウナ / GUMI

题目描述

这是一道交互题。

jt 有一个大小为 $n$ 的集合 $S$，集合中每个元素都是一个无序二元整数对 $(x, y)$，保证集合中 $1 \sim 2n$ 共 $2n$ 个整数每个恰好出现一次。

比如当 $n = 3$ 时，合法的集合 $S$ 可能是 $\{(1, 5), (2, 3), (4, 6)\}$。

开始时你只知道 $n$ 而不知道 $S$ 具体是什么。

现在支持一种操作：你可以给出 $i, j$（$1 \le i, j \le 2n$），然后 jt 会交换 $i, j$ 在 $S$ 中的位置（如 $i, j$ 在同一个二元组内，或 $i = j$，则什么也不会发生）。

比如，当 $S = \{(1, 5), (2, 3), (4, 6)\}$ 时，执行 $i = 2, j = 6$ 后 $S = \{(1, 5), (6, 3), (4, 2)\} = \{(1, 5), (2, 4), (3, 6)\}$。

在最开始时以及每次操作过后，对于当前的集合 $S$，jt 会告诉你 $res = \min\limits_{(x, y) \in S} \max(x, y)$。

比如，当 $S = \{(1, 5), (2, 3), (4, 6)\}$ 时，$res$ 为 $\min(\max(1, 5), \max(2, 3), \max(4, 6)) = \min(5, 3, 6) = 3$。

注意，每次 jt 告诉你 $res$ 之后不会撤销你做的操作，即你的操作是持续有效的。

你需要在 $lim$ 次操作内猜出初始的集合 $S$，即进行所有交换操作之前的版本。

保证初始的 $S$ 是提前确定的，即交互库不自适应。

交互方式

本题单个测试点内包含多组数据。

首先读入数据组数 $T$。

接下来有 $T$ 组数据，对于每组数据进行以下过程：

输入 $S$ 的大小 $n$ 以及 $lim$ 以开始交互。

每次操作，首先读入 $res$，接下来输出一行 ^ i j 表示你要执行操作 $i, j$。

在你确定答案后，请先输出一行一个 !，然后接下来 $n$ 行每行输出两个整数 x y 代表 $S$ 中的一个二元组，然后准备读入下一组数据。你可以以任意顺序输出这些二元组，且二元组内元素顺序可以任意。

在每次输出结束后，切记要输出换行符并刷新缓冲区：

• 在 C/C++ 中，使用 fflush(stdout)。
• 在 C++ 中，使用 std::cout.flush() 或 std::cout << std::flush。
• 在 Pascal 中，使用 flush(output)。
• 在 Python 中，使用 stdout.flush()。
• 其它语言请自行查阅文档。

当你在单个测试点所有测试数据的总操作次数不超过 $\boldsymbol{2.5 \times 10^5}$ 次时，保证交互库占用时间不超过 $8\operatorname s$，空间不超过 $128\operatorname{MB}$，也就是你至少能使用 $2 \operatorname{s}$ 的时间以及 $384\operatorname{MB}$ 的空间。

样例

2
3 100
3

3

4

2




1 0
2

^ 1 2

^ 3 6

^ 6 2

!
5 1
6 4
2 3


!
1 2

样例解释

注意，样例只是描述了一个可能发生的交互过程，并不一定存在逻辑（就是说答案可能是乱猜猜对的）。

对于第一组测试数据，$S$ 最开始为 $\{(1, 5), (2, 3), (4, 6)\}$，jt 告诉你 $res = 3$。

接下来你交换 $1, 2$，$S$ 变为 $\{(2, 5), (1, 3), (4, 6)\}$，jt 告诉你 $res = 3$。

接下来你交换 $3, 6$，$S$ 变为 $\{(2, 5), (1, 6), (3, 4)\}$，jt 告诉你 $res = 4$。

接下来你交换 $6, 2$，$S$ 变为 $\{(5, 6), (1, 2), (3, 4)\}$，jt 告诉你 $res = 2$。

你输出 $\{(5, 1), (6, 4), (2, 3)\}$，用了 $3$ 次操作，不超过 $lim = 100$ 次，回答正确。

对于第二组测试数据，$S$ 初始为 $\{(1, 2)\}$，你直接输出 $\{(1, 2)\}$，用了 $0$ 次操作，不超过 $lim = 0$ 次，回答正确。

数据范围

本题开启捆绑测试。

记 $\sum n$ 为单个测试点内所有的 $n$ 之和。

对于 $100\%$ 的数据，$1 \le T \le 10^5$，$1 \le n \le 5 \times 10^4$，$\sum n \le 10^5$。

子任务编号	$T$	$n$	$lim$	分数
$1$	$=1$		$=0$	$1$
$i$（$2 \le i \le 6$）	$=(2i-1)!!$	$=i$	$=10^9$	$8$
$7$	$\le 5$	$\le 100$	$=5n^2$	$14$
$8$	$\le 25$	$\le 10^3$	$=10n$	$15$
$9$	$\le 10^5$	$\le 5 \times 10^4$	$=\max(0, 2n - 3)$	$30$

$!!$ 代表双阶乘。