Щасливо-дужковий рядок

Limits: 2 sec., 512 MiB

Ця задача інтерактивна. Подбайте про виклик методу flush після виводу кожного рядка.

Зеник загадав щасливий рядок \(s\) з \(2n\) символів, серед яких рівно \(n\) символів 4 та \(n\) символів 7.

Марічка хоч і не знає, який рядок загадав Зеник, але хоче знайти такий порядок індексів, що, якщо переставити символи в цьому порядку, то вийде щасливо-дужковий рядок. Рядок \(t\) називається щасливо-дужковим, якщо на будь-якому його префіксі кількість 4 є не меншою ніж кількість 7. Більш формально, Марічка хоче знайти перестановку \(p\) довжини \(2n\) таку, що рядок \(s_{p_1}s_{p_2}\dots s_{p_{2n}}\) – щасливо-дужковий.

Перестановка довжини \(k\) — це така послідовність з \(k\) елементів, де всі елементи від 1 до \(k\) та всі елементи різні.

Щоб вгадати перестановку Марічка ставить запитання. Кожне запитання — це перестановка \(q\) з \(2n\) елементів. Зеник же відповідає, скільки є таких пар \(1 \le i<j \le 2n\), що \(s_{q_i}=7\) та \(s_{q_j}=4\). Назвемо такі пари інверсіями. Всього Марічка може задати не більше 200 таких запитань. Допоможіть їй знайти необхідний порядок індексів. Якщо порядків існує декілька, Марічка може вивести будь-який з них.

Взаємодія

Спочатку вам слід прочитати одне ціле число \(n\). Далі, щоб поставити питання, виведіть ? та \(2n\) чисел після того — перестановку \(q\). Після того зчитайте рядок з відповіддю, який містить одне число — кількість пар інверсій.

Коли ви уже впевнені, що знаєте необхідний порядок, виведіть ! та \(2n\) чисел після того — перестановку \(p\). Після цього ваша програма повинна завершити виконання.

Зауважте, що Зеник не може змінювати загаданий рядок після запитань Марічки, тобто інтерактор не адаптивний.

Constraints

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

Можна задати не більше 200 запитань.

Samples

Input (stdin) сopy	Output (stdout) сopy
2 2 4 3	? 1 2 3 4 ? 2 3 4 1 ? 2 4 3 1 ! 1 3 4 2

Notes

В першому прикладі Зеник загадав рядок 4774.

Розглянемо запитання Марічки:

• Марічка запитує оригінальний порядок, в ньому є 2 інверсії 4774 і 4774.

• Марічка запитує перестановку [2 3 4 1], якщо ми переставимо символи у рядку в такому порядку вийде 7744, в ньому є 4 інверсії.

• Марічка запитує перестановку [2 4 3 1], якщо ми переставимо символи у рядку в такому порядку вийде 7474, в ньому є 3 інверсії.

Далі Марічка уже знає цікавий їй порядок [1 3 4 2], який відповідає за рядок 4747. У цьому рядку на кожному префіксі кількість 4 є не меншою за кількість 7.