H1. Замок Баузера (Легкая версия)
ограничение по времени на тест
8 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Замок Баузера — Дани Донанди, Super Nintendo World: New Super Mario Bros. Wii

Это легкая версия задачи. Отличие между версиями заключается в том, что в этой версии $$$n \leq 70$$$ и вы можете сделать $$$10^4$$$ запросов. Вы можете делать взломы только в том случае, если решили все версии этой задачи.

Это интерактивная задача.

Пусть $$$n$$$ — положительное целое число. Функция от $$$n$$$ переменных $$$x_1, \ldots, x_n$$$ называется min-max, если ее можно построить, используя только вызовы $$$\min$$$ и $$$\max$$$ вокруг $$$x_1, \ldots, x_n$$$, при этом каждая переменная появляется ровно один раз в порядке слева направо в выражении. Например, $$$\min(x_1, x_2, x_3)$$$ является min-max функцией на $$$3$$$ переменных, но $$$\max(\min(x_1, x_3), x_2)$$$ и $$$\min(\max(x_1, x_2), \max(x_2, x_3))$$$ не являются.

Баузер выбрал min-max функцию на $$$n$$$ ($$$2 \leq n \leq 70$$$) переменных и сообщает вам $$$n$$$. Кроме того, он позволяет вам задавать запросы следующего вида: вы даете Баузеру $$$n$$$ целых чисел $$$x_1, \ldots, x_n$$$ ($$$1 \leq x_i \leq 10^9$$$) в качестве входных данных, и он сообщает вам $$$f(x_1, \ldots, x_n)$$$.

Чтобы сбежать из его замка, вам нужно выяснить его функцию, используя не более чем $$$10^4$$$ запросов в общей сложности. После этого, чтобы доказать ему, что вы узнали функцию, Баузер даст вам до $$$5000$$$ своих собственных входных данных $$$x_1, \ldots, x_n$$$, на которые вы должны ответить правильным значением $$$f(x_1, \ldots, x_n)$$$.

Поскольку замок Баузера очень защищен, у него на самом деле есть несколько функций, которые вам нужно выяснить, с общим количеством переменных не более $$$70$$$. Кроме того, он ограничивает вас использованием не более чем $$$10^4$$$ запросов по всем функциям и не будет задавать более $$$5000$$$ запросов в общей сложности.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 35$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$2 \leq n \leq 70$$$) — количество переменных в min-max функции.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$70$$$.

После того как вы прочитаете эту строку входных данных, взаимодействие начинается с вашего первого запроса.

Протокол взаимодействия

Чтобы сделать запрос, выведите строку (без кавычек) в следующем формате:

  • «? $$$x_1$$$ $$$x_2$$$ $$$\ldots$$$ $$$x_n$$$» ($$$1 \leq x_i \leq 10^9$$$).

Затем, после каждого запроса, прочитайте одно целое число — ответ на ваш запрос. Вы можете сделать до $$$10^4$$$ запросов такого типа в общей сложности по всем $$$t$$$ наборам.

Когда вы будете готовы начать отвечать на запросы Баузера, выведите строку, содержащую один символ «!» (без кавычек).

Каждый запрос Баузера содержит одну строку из $$$n$$$ целых чисел $$$x_1, x_2, \ldots, x_n$$$ ($$$1 \leq x_i \leq 10^9$$$) — входные данные Баузера. Гарантируется, что Баузер не задаст более $$$5000$$$ запросов в общей сложности по всем $$$t$$$ наборам.

После каждого запроса выведите одно целое число — значение $$$f(x_1, x_2, \ldots, x_n)$$$. Обратите внимание, что эти запросы являются онлайн, поэтому Баузер предоставит вам следующий запрос только после того, как вы ответите на его предыдущий запрос.

Когда Баузер закончит задавать запросы, вы получите одну строку, содержащую целое число $$$0$$$. После этого переходите к следующему набору или выходите, если это последний набор.

Взаимодействие в этой задаче является частично адаптивным. В частности, функции, которые выбирает Баузер, фиксированы в начале каждого взаимодействия, но его запросы к вам могут изменяться.

После вывода каждого запроса не забудьте вывести перевод строки и сбросить буфер вывода$$$^{\text{∗}}$$$. В противном случае вы получите вердикт Решение «зависло». На любом шаге взаимодействия, если вы считали $$$-1$$$ вместо корректных данных, ваше решение должно немедленно завершиться. Это означает, что ваше решение получит вердикт Неправильный ответ из-за некорректного запроса или любой другой ошибки. Если программа не завершится, вы можете получить любой вердикт, так как ваша программа продолжит чтение из закрытого потока.

Hacks

Для взломов, используйте следующий формат.

Первая строка должна содержать одно целое число $$$t$$$ ($$$1 \leq t \leq 35$$$) — количество наборов входных данных.

Первая строка каждого набора должна содержать одно целое число $$$n$$$ ($$$2 \leq n \leq 70$$$) — количество переменных в min-max функции.

Вторая строка каждого набора должна содержать серию разделенных пробелами токенов (без кавычек) из следующего списка, указывая min-max функцию:

  • «min»
  • «max»
  • «(»
  • «)»
  • «,»
  • положительные целые числа в диапазоне $$$1, 2, \ldots, n$$$.

Сумма $$$n$$$ по всем наборам не должна превышать $$$70$$$.

Например, тест, соответствующий примеру входных данных, выглядит следующим образом:

2
3
max ( 1 , 2 , 3 )
4
min ( max ( 1 , 2 ) , max ( 3 , 4 ) )

$$$^{\text{∗}}$$$Чтобы сбросить буфер вывода, используйте:

  • fflush(stdout) или cout.flush() в C++;
  • sys.stdout.flush() в Python;
  • смотрите документацию для других языков.
Пример
Входные данные
2
3

5

2

3 6 2

3 5 7

0
4

8

3

8 7 6 5

0
Выходные данные


? 5 4 3

? 1 2 1

!

6

7


? 1 9 8 7

? 5 1000000000 2 3

!

6
Примечание

В первом наборе min-max функция Баузера равна $$$f := \max(x_1, x_2, x_3)$$$. После того как были заданы два запроса, чтобы получить $$$f(5, 4, 3) = 5$$$ и $$$f(1, 2, 1) = 2$$$ от жюри, решение готово ответить на запросы жюри. Оно правильно определяет, что $$$f(3, 6, 2) = 6$$$ и $$$f(3, 5, 7) = 7$$$.

Во втором наборе min-max функция Баузера равна $$$f := \min(\max(x_1, x_2), \max(x_3, x_4))$$$. После того как были заданы два запроса, чтобы получить $$$f(1, 9, 8, 7) = 8$$$ и $$$f(5, 10^9, 2, 3) = 3$$$ от жюри, решение готово ответить на запросы жюри. Оно правильно определяет, что $$$f(8, 7, 6, 5) = 6$$$.

Обратите внимание, что не гарантируется, что запросы в примере уникально определяют min-max функцию. Пример приведен только для демонстрации того, как работают запросы. Пустые строки в примере входных и выходных данных даны только для лучшей читаемости; вам не нужно выводить их в вашем решении.