# Tubular Bells codeforces solution

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 nn tubes, and each of the tubes has a length that can be expressed by a integer from ll to rr 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 rl+1=nr−l+1=n.

Formally, we can say that Mike’s tubular bells are described by a permutation aa of length nn that contains all numbers from ll to rr inclusive, with aiai denoting the length of the ii-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 ll or rr. He will only tell you nn, and will allow you to ask no more than n+5000n+5000 queries.

In each query, you name two positive integers xxyy such that 1x,yn,xy1≤x,y≤n,x≠y. In response to this query, the program written by Mike will give you lcm(ax,ay)lcm(ax,ay), where lcm(c,d)lcm(c,d) denotes the least common multiple of cc and dd.

Solve Mike’s problem!

Input Tubular Bells solution codeforces

Each test contains multiple test cases.

The first line contains one positive integer tt (1t201≤t≤20), denoting the number of test cases. Description of the test cases follows.

The single line of each test case contains one positive integer nn (3n1053≤n≤105) — number of tubes in Mike’s tubular bells. Also 1lr21051≤l≤r≤2⋅105, i.e. the lengths of the tubes do not exceed 21052⋅105.

It is guaranteed that the sum of maximal number of queries (i.e. n+5000n+5000) over all test cases does not exceed 105+5000105+5000. It means that sum of nn does not exceed 105+5000t5000105+5000−t⋅5000.

Interaction

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

If you want to make a query, output it in the format “? xx yy“, where xx and yy — the numbers of tubes for which you learn the lcm (least common multiple) of their lengths. Note that 1x,yn,xy1≤x,y≤n,x≠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 “! a1a1 a2a2 … anan“. 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 tt (1t201≤t≤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 nn (3n1053≤n≤105) —the number of tubes. It is known that 1lr21051≤l≤r≤2⋅105, i.e. the lengths of the tubes do not exceed 21052⋅105.

The second line of each test case contains an array aa of nn positive integers — the lengths of the tubes in each input dataset. Remember that lairl≤ai≤r and rl+1=nr−l+1=n, and that all aiai are different.

Example Tubular Bells solution codeforces
input Tubular Bells solution codeforces

Copy Tubular Bells solution codeforces
3
5
8 10 7 6 9
5
24 25 28 27 26
7
1 2 3 4 5 6 7

output

Copy
? 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