Description

Xiao A has a permutation $a$ of length $n$, and he wants you to guess this permutation. You can only make the following two types of queries:

• ! x y: He will tell you the value of $a_x \bmod a_y$, where your query must satisfy $a_x\gt a_y$ and $x\ne y$; otherwise, he will get unhappy and directly judge the query as invalid, which will lead to WA.
• ? l S p: You need to give Xiao A a set $S$ of size $l$ and an integer $p$, where $S=\{x_1,x_2,x_3,\ldots,x_l\}$. For any $1\le i\le l$, $1\le x_i\le n$, and all $x_i$ are pairwise distinct. Also, it must satisfy $1\le p\le n$ and $1\le l\le n$. Xiao A will tell you all $x_k$ in this set such that $a_{x_k} \ge p$, returning in the following form: first an integer $L$, then $L$ integers, indicating that there are $L$ such $k$ (note that what is returned are the elements of the set $S$, not the indices within $S$).

You can ask at most $m_1$ queries of type $1$ and $m_2$ queries of type $2$. In addition, for type $2$ queries, the sum of the sizes of the queried sets must not exceed $m_3$, in order to guess the sequence.

Input Format

Input the permutation length $n$ and $m_1,m_2,m_3$ to start the interaction.

During the interaction, you may make the two types of queries described above. Whether it is the first type of query or the second type of query, the interactive library will return an integer.

After you are sure of the answer, output one line in the form A a[1] a[2] ... a[n-1] a[n] to stop the interaction.

After you output a line, flush the buffer:

• In C++, use fflush(stdout) or cout.flush().
• In Pascal, use flush(output).
• In Python, use stdout.flush().
• For other languages, please check the documentation yourself.

Output Format

See "Interaction Method".

3 100 100 100

1 3

1 2

? 3 1 2 3 3

? 2 1 2 2

A 1 2 3

Hint

【Constraints】

This problem uses bundled testdata.

A: The permutation $a$ is guaranteed to be constructed randomly.

【Notes】

1. Making an invalid query, or continuing to query after the interactive library has output more than $m$ numbers, will directly lead to WA.

2. The top row in the Constraints table uses $=$, not $\le$.

Translated by ChatGPT 5