Codeforces Round 922 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

constructive algorithms

divide and conquer

implementation

interactive

probabilities

sortings

*2200

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. ace5 and Task Order

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThis is an interactive problem!

In the new round, there were $$$n$$$ tasks with difficulties from $$$1$$$ to $$$n$$$. The coordinator, who decided to have the first round with tasks in unsorted order of difficulty, rearranged the tasks, resulting in a permutation of difficulties from $$$1$$$ to $$$n$$$. After that, the coordinator challenged ace5 to guess the permutation in the following way.

Initially, the coordinator chooses a number $$$x$$$ from $$$1$$$ to $$$n$$$.

ace5 can make queries of the form: $$$?\ i$$$. The answer will be:

- $$$>$$$, if $$$a_i > x$$$, after which $$$x$$$ increases by $$$1$$$.
- $$$<$$$, if $$$a_i < x$$$, after which $$$x$$$ decreases by $$$1$$$.
- $$$=$$$, if $$$a_i = x$$$, after which $$$x$$$ remains unchanged.

The task for ace5 is to guess the permutation in no more than $$$40n$$$ queries. Since ace5 is too busy writing the announcement, he has entrusted this task to you.

Input

The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases.

Interaction

The interaction between your program and the jury's program begins with reading a positive integer $$$n$$$ ($$$1 \leq n \leq 2000$$$) — the length of the hidden permutation.

To make a query, output a line in the format "? i", where $$$1 \leq i \leq n$$$.

As an answer, you will receive:

- ">", if $$$a_i$$$ > $$$x$$$, after which $$$x$$$ will increase by $$$1$$$.
- "<", if $$$a_i$$$ < $$$x$$$, after which $$$x$$$ will decrease by $$$1$$$.
- "=", if $$$a_i$$$ = $$$x$$$, after which $$$x$$$ will remain unchanged.

You can make no more than $$$40n$$$ queries. To output the answer, you need to print "! a_1 a_2 ... a_n", where $$$1 \leq a_i \leq n$$$, and all of them are distinct. Outputting the answer does not count as a query.

If your program makes more than $$$40n$$$ queries for one test case, or makes an invalid query, then the response to the query will be -1. After receiving such a response, your program should immediately terminate to receive the verdict Wrong Answer. Otherwise, it may receive any other verdict.

After outputting a query, do not forget to print a newline and flush the output buffer. Otherwise, you will receive the verdict Presentation Error. To flush the buffer, use:

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

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2000$$$.

The interactor in this problem is not adaptive.

Hacks:

To make a hack, use the following format:

The first line contains a single integer $$$t$$$ — the number of test cases.

The description of each test case should consist of two lines. The first line contains the numbers $$$n$$$ and $$$x$$$ ($$$1 \leq x \leq n \leq 2000$$$) — the length of the hidden permutation and the initial value of the number $$$x$$$. The second line contains $$$n$$$ distinct numbers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$) — the permutation that the jury should choose in this test case.

Sum of $$$n$$$ over all test cases should not exceed $$$2000$$$.

Example

Input

2 5 > = < = < < 2 >

Output

? 4 ? 2 ? 1 ? 5 ? 1 ? 3 ! 2 4 1 5 3 ? 1 ! 2 1

Note

In the first test, the hidden permutation is $$$a$$$ = [$$$2,4,1,5,3$$$], and the initial value of $$$x$$$ is $$$3$$$.

In the second test, the hidden permutation is $$$a$$$ = [$$$2,1$$$], and the initial value of $$$x$$$ is $$$1$$$.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/13/2024 09:19:37 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|