Background

The background of this problem is not entirely fictional and does not imply anything about any real person..

Xiao L was the “white moonlight” (baiyueguang) of Xiao L in middle school.

One day, Xiao L said on Moments that they wanted to play “Nong”, and Xiao L quickly studied how to download Honor of Kings.

The next day, Xiao L said on Moments that they wanted to play PUBG, and Xiao L quickly studied how to download PUBG.

But Xiao L soon broke up with Xiao L. Xiao L’s last feelings turned into a permutation. Unfortunately, Xiao L was not willing to tell everyone.

However, after your constant questioning, Xiao L finally agreed to answer a few questions about the permutation.

Problem Description

There is a hidden permutation $p$ of length $n$. You may perform the following queries any number of times: choose a triple $(l, r, k)$ satisfying $1 \le l \le r \le n$, $1 \le k \le r - l + 1$. The interactive judge will return the $k$-th largest value among indices in $[l, r]$.

For one query, the cost is $\frac{1}{r - l + 1}$. You need to determine the permutation within a total cost not exceeding $11.8$.

The interactive judge is non-adaptive. That is, the permutation you need to find is already fixed before the interaction starts.

Input Format

The first line contains a positive integer $t$ ($1 \le t \le 5$), the number of test cases.

For each test case, one line contains $n$ ($1 \le n \le 1000$), the length of the permutation $p$.

When you have determined the permutation, you should output in the form ! p1 p2 ... pn to indicate the permutation you found.

This problem uses IO interactive mode.

Interaction Format

• ? l r k: query the $k$-th largest value among indices in $[l, r]$.

• ! p1 p2 p3 ... pn: output the answer.

Please note: in each test case, ensure that the total cost of all queries does not exceed $11.8$.

Also note that after each operation, you need to call the following function to flush the output buffer:

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

For other languages, please refer to the corresponding language documentation.

Output Format

See “Interaction Format”.

1
5

2

3

1

4

? 1 1 1

? 2 2 1

? 3 3 1

? 4 4 1

! 2 3 1 4 5

Hint

Translated by ChatGPT 5