Interactive Color Ball Guessing

This is an interactive problem.

There are \(N\) balls numbered from \(1\) to \(N\). You can ask queries about the number of different colors in a given range.

In each query, you will print a line in the format: ? l r which asks for the number of distinct colors among the balls from index \(l\) to index \(r\) (inclusive). Once you have deduced the color of every ball, you should output the answer in the following format:

! a_1 a_2 \dots a_N

Note that since the actual color values are hidden, you only need to assign a unique integer (between 1 and \(N\)) to each distinct color such that:

• \(1 \leq a_i \leq N\) for all \(i\);
• If two balls have the same color, then they must be assigned the same integer;
• If two balls have different colors, then they must be assigned different integers.

You are allowed at most \(Q\) queries.

Interaction format:

1. The first line of input contains a positive integer \(T\), which represents the subtask number (and not the number of test cases).
2. The second line contains two integers \(N\) and \(Q\), representing the number of balls and the query limit respectively.
3. You may then ask up to \(Q\) queries by printing lines in the format ? l r and reading the answer from the judge.
4. When you have determined the color of every ball, print a line in the format ! a_1 a_2 \dots a_N.
5. After each output, make sure to flush the output buffer (for example, in Python, call stdout.flush()).

Note: In this problem, due to its interactive nature, the sample solution provided below reads the correct ball colors directly from the input. In a real interactive environment, you would instead deduce these colors by making queries. In our offline simulation for testing purposes, the ball colors are appended after the initial input.

inputFormat

The input begins with a line containing a positive integer \(T\) (the subtask number).

The second line contains two integers \(N\) and \(Q\): the number of balls and the maximum number of queries allowed.

For offline simulation purposes (since this is originally interactive), the next line contains \(N\) integers representing the hidden colors of the balls. In a real interactive judge these would not be provided directly.

outputFormat

When your program is ready to output the final answer, it should print one line in the format:

! a_1 a_2 ... a_N

where each \(a_i\) is a positive integer between \(1\) and \(N\). All balls of the same color must have the same value, and balls of different colors must have different values.

sample

1
3 100
1 2 1

! 1 2 1

</p>