Знаете ли вы, что такое оркестровые колокола? Это музыкальный инструмент, состоящий из цилиндрических металлических трубок. В оркестре колокола имитируют колокольный звон.
У Майка тоже есть оркестровые колокола! Они состоят из \(n\) трубок, причем каждая из трубок имеет длину, которая может быть выражена целым числом от \(l\) до \(r\) включительно. Ясно, что длины всех трубок различны (нет смысла делать одинаковые трубки). Также известно, что \(r-l+1 = n\).
Формально, можно сказать, что оркестровые колокола Майка описываются перестановкой \(a\) длины \(n\), которая содержит все числа от \(l\) до \(r\) включительно, причем \(a_i\) обозначает длину \(i\)-й трубки.
Вам предлагается интересная задача: угадать, как выглядит инструмент Майка. Проще говоря, необходимо угадать перестановку.
Майк не скажет вам ни \(l\), ни \(r\). Он скажет вам только \(n\), и разрешит задать не более, чем \(n + 5000\) запросов.
В каждом запросе вы называете два целых положительных числа \(x\), \(y\) таких, что \(1 \le x, y \le n, x \neq y\). В ответ на этот запрос программа, написанная Майком, выдаст вам \(\mathrm{lcm}(a_x, a_y)\), где \(\mathrm{lcm}(c,d)\) обозначает наименьшее общее кратное (НОК) чисел \(c\) и \(d\).
Решите задачу Майка!
Протокол взаимодействия
Для каждого набора входных данных считайте одно целое число \(n\). Вам разрешено сделать не более \(n + 5000\) запросов.
Если вы хотите сделать запрос, выведите его в формате «? \(x\) \(y\)», где \(x\) и \(y\) — номера трубок, для которых вы узнаете НОК их длин. Обратите внимание, что должно выполняться \(1 \le x, y \le n, x \neq y\). Интерактор вернет вам в качестве ответа одно целое число — ответ на ваш запрос.
Если вы готовы вывести ответ, выводите его в формате «! \(a_1\) \(a_2\) ... \(a_n\)». Вывод ответа не считается запросом и не включается в количество допустимых запросов.
После каждого запроса и вывода ответа не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт «решение зависло». Для сброса буфера используйте:
- fflush(stdout) или cout.flush() в C++;
- System.out.flush() в Java;
- flush(output) в Pascal;
- stdout.flush() в Python;
- смотрите документацию для других языков.
Обратите внимание, что интерактор не адаптивен. Это означает, что перестановка изначально фиксирована и не зависит от ваших запросов.
Взломы:
Для взломов используйте следующий формат:
В первой строке находится одно целое положительное число \(t\) (\(1 \le t \le 20\)) — количество наборов входных данных. Описание наборов входных данных приведено ниже.
В первой строке каждого набора входных данных находится одно целое положительное число \(n\) (\(3 \le n \le 10^5\)) — количество трубок. Известно, что \(1 \le l \le r \le 2 \cdot 10^5\), т.е. длины трубок не превосходят \(2 \cdot 10^5\).
Во второй строке каждого набора входных данных находится массив \(a\) из \(n\) целых положительных чисел — длины трубок. Помните, что \(l \le a_i \le r\) и \(r-l+1 = n\), а также то, что все \(a_i\) различны.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
5
8 10 7 6 9
5
24 25 28 27 26
7
1 2 3 4 5 6 7
|
? 1 2
40
? 2 5
90
? 3 1
56
? 4 5
18
! 8 10 7 6 9
? 1 5
312
? 2 4
675
! 24 25 28 27 26
? 1 4
4
? 2 5
10
? 3 7
21
? 6 2
6
? 2 5
10
? 1 2
2
? 1 2
2
? 1 2
2
? 1 2
2
? 1 2
2
! 1 2 3 4 5 6 7
|