Вгадай дерево

Це інтерактивна задача.

Після великої битви, що знищила планетарну систему Link-Cut, місцеві жителі попросили вас допомогти відновити її. На жаль, майже вся інформація про те, як вона виглядала, зникла. Проте, маг Фрусі знову прийшов вам на допомогу! Він виявив магічну туманність, яка пам'ятає, як система виглядала до битви.

Планетарну систему Link-Cut можна представити у вигляді дерева, що складається з $n$ вершин. Для одного запиту до туманності ви можете надати перестановку вершин дерева $p$. У відповідь на запит ви отримуєте масив $a$, де $a_i$ представляє кількість зв'язаних компонентів у лісі, отриманому шляхом розгляду лише вершин $p_1$, $p_2$, $\dots$, $p_i$.

Оскільки кожен запит коштує Фрусі значну кількість мани, ви можете зробити не більше $Q$ запитів.

Інтерактор не адаптивний!

Вхідні дані

Перший рядок містить лише одне число $n(2\le n\le 2000)$.

Протокол взаємодії

Щоб виконати запит, виведіть "? $p_1$ $p_2$ $\dots$ $p_n$", де $p$ - це перестановка.

У відповідь на запит програма журі виведе масив $a$, де кожен елемент буде розділений пробілом.

Якщо запит є недійсним (тобто, перевищено максимальну кількість запитів або параметри запиту недійсні), програма журі виведе -1 і завершить роботу. У цьому випадку заверште свою програму, щоб отримати вердикт Неправильна відповідь.

Обов'язково викликайте метод flush після виведення кожного рядка. Ви можете використовувати:

• fflush(stdout), cout << endl, або cout.flush() в C++;

• System.out.flush() в Java;

• flush(output) в Pascal;

• sys.stdout.flush() в Python;

• консультуйтеся з документацією для інших мов програмування.

Вихідні дані

Щоб дати відповідь, виведіть у першому рядку "!", а в наступних $n-1$ рядках - ребро, представлене двома цілими числами $u$ та $v$, дерева в будь-якому порядку.

Приклади

5

1 1 1 1 1

1 2 3 3 1

? 1 2 3 4 5

? 4 5 1 2 3

!
1 2 
4 3
3 1
3 5

Примітка

Це зображення відповідає другому запиту та префіксу довжини $3$. Ми виділили вершини $[4,5,1]$, в результаті чого отримали $3$ зв'язані компоненти.

Оцінювання

1. ($12$ балів): $n\le 100$, $Q=max(50,n^2)$;

2. ($13$ балів): $n\le 200$, $Q=max(50,12n)$;

3. ($21$ бал): $n\le 500$, $Q=max(50,2n+2)$;

4. ($32$ бали): $n\le 1000$, $Q=max(50,n)$;

5. ($30$ балів): Дерево - це бамбук (кожна вершина має не більше двох сусідів), $Q=\lfloor \frac{n}{2}\rfloor +50$;

6. ($52$ бали): $Q=\lfloor \frac{n}{2}\rfloor +50$;

7. ($90$ балів): $Q=50$;