Lucky-bracket string

Limits: 2 sec., 512 MiB

This statement was translated automatically from Ukrainian.

This problem is interactive. Make sure to call the flush method after outputting each line.

Zenyk thought of a lucky string \(s\) consisting of \(2n\) characters, of which exactly \(n\) are characters 4 and \(n\) are characters 7.

Marichka does not know which string Zenyk thought of, but she wants to find an order of indices such that if the characters are rearranged in this order, the result is a lucky-bracket string. A string \(t\) is called a lucky-bracket string if on any of its prefixes the number of 4s is greater than or equal to the number of 7s. More formally, Marichka wants to find a permutation \(p\) of length \(2n\) such that the string \(s_{p_1}s_{p_2}\dots s_{p_{2n}}\) is lucky-bracket.

A permutation of length \(k\) is a sequence of \(k\) elements where all elements are from 1 to \(k\) and all elements are distinct.

To guess the permutation, Marichka asks questions. Each question is a permutation \(q\) of \(2n\) elements. Zenyk answers how many pairs \(1 \le i<j \le 2n\) exist such that \(s_{q_i}=7\) and \(s_{q_j}=4\). Let’s call such pairs inversions. Marichka can ask at most 200 such questions in total. Help her find the required order of indices. If there are multiple such orders, Marichka can output any of them.

Interaction

First, you need to read a single integer \(n\). Then, to ask a question, print ? followed by \(2n\) numbers — the permutation \(q\). After that, read the response string, which contains a single number — the number of inversion pairs.

When you are confident that you know the required order, print ! followed by \(2n\) numbers — the permutation \(p\). After this, your program should terminate.

Note that Zenyk cannot change the chosen string after Marichka’s questions, meaning the interactor is non-adaptive.

Constraints

\(1 \le n \le 10^4\),

You can ask at most 200 questions.

Samples

Notes

In the first example, Zenyk thought of the string 4774.

Let’s consider Marichka’s questions:

• Marichka asks the original order, in it there are 2 inversions 4774 and 4774.

• Marichka asks the permutation [2 3 4 1], if we rearrange the characters in the string in this order we get 7744, in it there are 4 inversions.

• Marichka asks the permutation [2 4 3 1], if we rearrange the characters in the string in this order we get 7474, in it there are 3 inversions.

Then Marichka already knows the order of interest to her [1 3 4 2], which corresponds to the string 4747. In this string, on each prefix, the number of 4s is greater than or equal to the number of 7s.