Это интерактивная задача.
В гонках участвует \(n^2\) пепе, пронумерованных \(1, 2, \ldots, n^2\), с попарно различными скоростями. Вы хотите устроить несколько гонок, чтобы выяснить относительную скорость всех пепе.
В одной гонке можно выбрать ровно \(n\) различных пепе и заставить их соревноваться друг с другом. После каждого заезда вы узнаете только самого быстрого пепе среди этих \(n\) пепе.
Сможете ли вы найти порядок \(n^2-n+1\) самых быстрых пепе за не более чем \(2n^2 - 2n + 1\) заездов? Заметим, что самые медленные \(n - 1\) пепе неотличимы друг от друга.
Заметим, что интерактор является адаптивным. То есть относительные скорости пепе изначально не фиксированы и могут зависеть от ваших запросов. Но гарантируется, что в любой момент времени существует хотя бы одна начальная конфигурация пепе такая, что все ответы на запросы корректны.
Протокол взаимодействия
Чтобы задать гонку, выведите строку следующего формата:
- \(\mathtt{?}\,x_1\,x_2 \ldots x_n\) (\(1 \le x_i \le n^2\), \(x_i\) попарно различны) — номера пепе, которые должны участвовать в гонке.
После каждого заезда необходимо считать строку, содержащую единственное целое число \(p\) (\(1\le p\le n^2\)) — самого быстрого пепе в гонке.
Когда вы узнаете \(n^2-n+1\) самых быстрых пепе, выведите одну строку следующего формата:
- \(\mathtt{!}\,p_1\,p_2 \ldots p_{n^2 - n + 1}\) (\(1 \le p_i \le n^2\), \(p_i\) попарно различны)
где
\(p\) — последовательность номеров этих пепе в порядке убывания скорости.
После этого переходите к следующему набору входных данных или завершайте работу программы, если наборов входных данных больше не осталось.
Если ваша программа выполнит более \(2n^2 - 2n + 1\) заездов для одного набора входных данных или сделает некорректный заезд, то вы можете получить вердикт «Неправильный ответ».
После вывода запроса или ответа не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:
- fflush(stdout) или cout.flush() в C++;
- System.out.flush() в Java;
- flush(output) в Pascal;
- stdout.flush() в Python;
- смотрите документацию для других языков.
Формат взломов
Для взломов используйте следующий формат:
Первая строка должна содержать \(t\) — количество наборов входных данных.
Первая строка каждого набора входных данных должна содержать целое число \(n\), за которым следует строка manual.
Вторая строка каждого набора входных данных должна содержать перестановку \(a_1,a_2,\ldots,a_{n^2}\) целых чисел от \(1\) до \(n^2\). \(a_i > a_j\) тогда и только тогда, когда пепе \(i\) имеет скорость больше, чем пепе \(j\).
Например, формат взлома для примера имеет следующий вид: \(\mathtt{1}\\\mathtt{2}~\mathtt{manual}\\\mathtt{1}~\mathtt{2}~\mathtt{3}~\mathtt{4}\)