Tubular Bells
Contest: Codeforces Round 741 (Div. 2)
Difficulty rating: 2900
Tags: interactive, math, number theory, probabilities

Do you know what tubular bells are? They are a musical instrument made up of cylindrical metal tubes. In an orchestra, tubular bells are used to mimic the ringing of bells.

Mike has tubular bells, too! They consist of $$$n$$$ tubes, and each of the tubes has a length that can be expressed by a integer from $$$l$$$ to $$$r$$$ inclusive. It is clear that the lengths of all the tubes are different (it makes no sense to make the same tubes). It is also known that $$$r-l+1 = n$$$.

Formally, we can say that Mike's tubular bells are described by a permutation $$$a$$$ of length $$$n$$$ that contains all numbers from $$$l$$$ to $$$r$$$ inclusive, with $$$a_i$$$ denoting the length of the $$$i$$$-th tube.

You are offered an interesting task: to guess what Mike's instrument looks like. Simply, you must guess the permutation.

Mike won't tell you $$$l$$$ or $$$r$$$. He will only tell you $$$n$$$, and will allow you to ask no more than $$$n + 5000$$$ queries.

In each query, you name two positive integers $$$x$$$, $$$y$$$ such that $$$1 \le x, y \le n, x \neq y$$$. In response to this query, the program written by Mike will give you $$$\mathrm{lcm}(a_x, a_y)$$$, where $$$\mathrm{lcm}(c,d)$$$ denotes the least common multiple of $$$c$$$ and $$$d$$$.

Solve Mike's problem!

Input format:
Each test contains multiple test cases.

The first line contains one positive integer $$$t$$$ ($$$1 \le t \le 20$$$), denoting the number of test cases. Description of the test cases follows.

The single line of each test case contains one positive integer $$$n$$$ ($$$3 \le n \le 10^5$$$) — number of tubes in Mike's tubular bells. Also $$$1 \le l \le r \le 2 \cdot 10^5$$$, i.e. the lengths of the tubes do not exceed $$$2 \cdot 10^5$$$.

It is guaranteed that the sum of maximal number of queries (i.e. $$$n + 5000$$$) over all test cases does not exceed $$$10^5 + 5000$$$. It means that sum of $$$n$$$ does not exceed $$$10^5 + 5000 - t \cdot 5000$$$.

Interaction format:
For each set of input data, read one integer $$$n$$$. You are allowed to make no more than $$$n + 5000$$$ queries.

If you want to make a query, output it in the format "? $$$x$$$ $$$y$$$", where $$$x$$$ and $$$y$$$ — the numbers of tubes for which you learn the lcm (least common multiple) of their lengths. Note that $$$1 \le x, y \le n, x \neq y$$$ must be satisfied. The interactor will return a single integer —the answer to your query.

If you are ready to print the answer, print it in the format "! $$$a_1$$$ $$$a_2$$$ ... $$$a_n$$$". The output of the answer is not considered a query and is not included in the number of queries.

After each query and answer output, don't forget to output the line translation and reset the output buffer. Otherwise you will get the verdict "Idleness limit exceeded". To reset the buffer use:

- fflush(stdout) or cout.flush() in C++;
- System.out.flush() in Java;
- flush(output) in Pascal;
- stdout.flush() in Python;
- see documentation for other languages.

Note that the interactor is not adaptive. That is, the original permutation is fixed in the beginning and don't depend on your queries.

Hacks:

Use the following format for hacks:

The first line contains a single positive integer $$$t$$$ ($$$1 \le t \le 20$$$) — the number of input datasets. A description of the input data sets is given below.

The first line of each test case contains one positive integer $$$n$$$ ($$$3 \le n \le 10^5$$$) —the number of tubes. It is known that $$$1 \le l \le r \le 2 \cdot 10^5$$$, i.e. the lengths of the tubes do not exceed $$$2 \cdot 10^5$$$.

The second line of each test case contains an array $$$a$$$ of $$$n$$$ positive integers — the lengths of the tubes in each input dataset. Remember that $$$l \le a_i \le r$$$ and $$$r-l+1 = n$$$, and that all $$$a_i$$$ are different.

Constraints:
Time limit: 5.0 s
Memory limit: 512.0 MB

Example input:
3
5
8 10 7 6 9
5
24 25 28 27 26
7
1 2 3 4 5 6 7

Example output:
? 1 2
40
? 2 5
90
? 3 1
56
? 4 5
18
! 8 10 7 6 9
? 1 5
312
? 2 4
675
! 24 25 28 27 26
? 1 4
4
? 2 5
10
? 3 7
21
? 6 2
6
? 2 5
10
? 1 2
2
? 1 2
2
? 1 2
2
? 1 2
2
? 1 2
2
! 1 2 3 4 5 6 7

Editorial:
As I know, there are simpler solutions to this problem, but I will describe my solution.
We can assume the whole array is randomly permutated, because we can make queries by renumbering it. We also pre-calculate all prime numbers smaller than $$$200000$$$.
Let us denote something: $$$n$$$ — the number of numbers in the array, $$$a$$$ — the array itself, $$$l$$$ — the smallest value in the array, $$$r$$$ — the largest value in the array.
So let's look at three cases:
• $$$n < 100$$$. We use the following simple solution: find out the lcm of all pairs of numbers. The greatest of these values will give us the pair of numbers $$$r-1$$$ and $$$r$$$. It is easy to find out which number $$$r$$$ is: all pairs of lcms of this number with others will be divisible by $$$r$$$. Now exclude $$$r$$$ from the array, and exclude all pairwise lcms with it. The highest value will give us a pair $$$r-1$$$ and $$$r-2$$$. Repeat this algorithm until all numbers are found.
• $$$100 \le n < 10000$$$. Solve for $$$\lceil\frac{3n}{2}\rceil$$$ queries. We ask for lcms of pairs of numbers: the first with the second, the third with the fourth, etc. Now we will look for the maximal prime multiplier in each such lcm. We will do it by using pre-calculated prime numbers. Since the array is randomly permutated, this will work in a reasonable amount of time. When we will find a pair of numbers with the greatest prime number, we easily find out which of these two numbers is the greatest prime: ask the lcm of one of the numbers in the pair with any other number and check if that lcm contains that greatest prime number. Finding the largest prime number, we easily find out the remaining array: $$$a_i = lcm(a_i, p) / p$$$, where $$$p$$$ –that prime number.
• $$$10000 \le n \le 100000$$$. Let $$$c$$$ = $$$500$$$. This number is chosen so that $$$c^2 > 200000$$$. We will search the array for any prime number that is greater than $$$c$$$. Do the following: randomly ask pairs of numbers until we find one that has only two prime numbers in the factorization of the lcm, and both of these prime numbers are greater than $$$c$$$. Let it be $$$p_1$$$ and $$$p_2$$$. Then one of the numbers in the pair — $$$p_1$$$ and the other  — $$$p_2$$$. To find out which number is which, let's ask the lcm of one of them with some numbers chosen at random, and check what all those lcms are divisible by. If they are all divisible by $$$p_1$$$, then the chosen number is $$$p_1$$$, otherwise it is $$$p_2$$$. The chance of us guessing wrong is extremely small, because it requires that all the chosen numbers are divisible by $$$p_2$$$, and the chance of that is negligible.We have found a prime number greater than $$$c$$$. Let it be $$$p$$$. Now we can find out all the numbers that are not divisible by $$$p$$$ and greater than $$$c$$$. To do this, we ask all the NOCs of the number $$$p$$$ and the other numbers. And now, if $$$lcm(p, a_i) / p > c$$$, then $$$a_i = lcm(p, a_i) / p$$$. This is because if $$$a_i$$$ is divisible by $$$p$$$, then $$$lcm(p, a_i) / p = a_i / p \le c$$$. If $$$a_i$$$ is not divisible by $$$p$$$, then by dividing the lcm by $$$p$$$ we will find $$$a_i$$$, since the number $$$p$$$ is prime.Find the largest prime among the found numbers, and use it to find the remaining numbers as described above. Since we only need to find all numbers divisible by $$$p$$$ and all numbers not exceeding $$$c$$$, such queries will be no more than $$$100000 / 500 + 500 = 700$$$.