Problem Description

This is an interactive problem.

There are $N$ balls, numbered from $1$ to $N$.

Each time, you may ask how many different colors appear among the balls whose indices are in $[l,r]$. You need to determine the color of every ball. Since you do not know what the actual colors are, you only need to use the same number to represent the same color.

Input Format

See “Interaction Format”.

Output Format

See “Interaction Format”.

1
5 10000

2

1

2
 

 

? 1 5

? 1 3

? 2 4

! 1 1 1 2 2

Hint

Constraints

This problem uses bundled testdata.

• Subtask 1 (8 points): $Q=10000$, it is guaranteed that the indices of balls of each color form a contiguous segment.
• Subtask 2 (7 points): $Q=2000$, it is guaranteed that the indices of balls of each color form a contiguous segment.
• Subtask 3 (19 points): $Q=2000$, it is guaranteed that there are at most $3$ colors in total.
• Subtask 4 (14 points): $Q=2000$, it is guaranteed that there are at most $4$ colors in total.
• Subtask 5 (12 points): $Q=2000$, it is guaranteed that there are at least $(N-1)$ colors in total.
• Subtask 6 (21 points): $Q=10000$, it is guaranteed that $N\le 100$.
• Subtask 7 (19 points): $Q=10000$.

For all testdata, it is guaranteed that $1\leq T\leq 7$ and $2\leq N\leq 10^3$.

Input Format

See “Interaction Format”.

Output Format

See “Interaction Format”.

Hint

Interaction Format

The first line contains a positive integer $T$, which represents the Subtask ID (not the number of test cases).

The second line contains two integers $N,Q$, representing the number of balls and the query limit.

Next, you may make at most $Q$ queries and read the answers returned by the interactor. Each query should be in the format ? l r, meaning you ask for the number of colors among the balls in $[l,r]$.

When you are sure about the colors of all balls, you should output ! a1 a2 ... an to represent the colors of all balls. You must ensure that:

• $1\leq a_i\leq N$ and all $a_i$ are integers.
• Balls with the same color have the same $a_i$.
• Balls with different colors have different $a_i$.

After each output, you must flush the buffer. You may use the following statements to flush:

• 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 check the documentation for the corresponding language.

Translated by ChatGPT 5