Background

Original problem link: https://oier.team/problems/S3C。

Problem Description

This is an interactive problem.

jt has a set $S$ of size $n$. Each element in the set is an unordered integer pair $(x, y)$. It is guaranteed that among the $2n$ integers from $1$ to $2n$, each appears exactly once in the set.

For example, when $n = 3$, a valid set $S$ could be $\{(1, 5), (2, 3), (4, 6)\}$.

At the beginning, you only know $n$, but you do not know what $S$ is.

Now one kind of operation is supported: you can give $i, j$ ($1 \le i, j \le 2n$), then jt will swap the positions of $i$ and $j$ in $S$ (if $i, j$ are in the same pair, or $i = j$, then nothing happens).

For example, when $S = \{(1, 5), (2, 3), (4, 6)\}$, after performing $i = 2, j = 6$, we have $S = \{(1, 5), (6, 3), (4, 2)\} = \{(1, 5), (2, 4), (3, 6)\}$.

At the very beginning and after each operation, for the current set $S$, jt will tell you

For example, when $S = \{(1, 5), (2, 3), (4, 6)\}$, we have $res = \min(\max(1, 5), \max(2, 3), \max(4, 6)) = \min(5, 3, 6) = 3$.

Note that after jt tells you $res$ each time, jt will not undo the operations you made, i.e. your operations remain effective.

You need to guess the initial set $S$ within $lim$ operations, i.e. the version before any swap operations.

It is guaranteed that the initial $S$ is fixed in advance, i.e. the interactor is not adaptive.

Interaction

This problem contains multiple test cases in a single test file.

First read the number of test cases $T$.

Then there are $T$ test cases. For each test case, do the following process:

Input the size $n$ of $S$ and $lim$ to start the interaction.

For each operation, first read $res$, then output one line ^ i j to indicate that you want to perform the operation on $i, j$.

After you have determined the answer, first output one line containing a single !, then output $n$ lines, each with two integers x y representing one pair in $S$, and then get ready to read the next test case. You may output these pairs in any order, and the order inside each pair can also be arbitrary.

After each line you output, please flush the buffer:

• In C++, use fflush(stdout) or cout.flush().
• In Pascal, use flush(output).
• In Python, use stdout.flush().
• For other languages, please check the documentation yourself.

When the total number of operations over all testdata in a single test point does not exceed $\boldsymbol{2.5 \times 10^5}$, it is guaranteed that the interactor runs within $1\operatorname s$ time and $128\operatorname{MB}$ memory. That is, you can use at least $1 \operatorname{s}$ of time and $384\operatorname{MB}$ of memory.

Input Format

See "Interaction".

Output Format

See "Interaction".

2
3 100
3

3

4

2




1 0
2

^ 1 2

^ 3 6

^ 6 2

!
5 1
6 4
2 3


!
1 2

Hint

Sample Explanation

Note that the sample only describes one possible interaction process, and it may not be logically consistent (that is, the answer might be a random guess that happens to be correct).

For the first test case, initially $S = \{(1, 5), (2, 3), (4, 6)\}$, and jt tells you $res = 3$.

Then you swap $1, 2$, $S$ becomes $\{(2, 5), (1, 3), (4, 6)\}$, and jt tells you $res = 3$.

Then you swap $3, 6$, $S$ becomes $\{(2, 5), (1, 6), (3, 4)\}$, and jt tells you $res = 4$.

Then you swap $6, 2$, $S$ becomes $\{(5, 6), (1, 2), (3, 4)\}$, and jt tells you $res = 2$.

You output $\{(5, 1), (6, 4), (2, 3)\}$. You used $3$ operations, which does not exceed $lim = 100$, so the answer is correct.

For the second test case, initially $S = \{(1, 2)\}$. You directly output $\{(1, 2)\}$. You used $0$ operations, which does not exceed $lim = 0$, so the answer is correct.

Constraints

This problem uses bundled tests.

Let $\sum n$ be the sum of all $n$ within a single test point.

For $100\%$ of the data, $1 \le T \le 10^5$, $1 \le n \le 5 \times 10^4$, $\sum n \le 10^5$.

$!!$ means double factorial。

Translated by ChatGPT 5