D1. Из неизвестного (простая версия)
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это простая версия задачи. Отличие между версиями заключается в том, что в этой версии нет ограничений на сумму длин статей по всем запросам. Вы можете делать взломы только в том случае, если решили все версии этой задачи.

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

Команда RiOI недавно разработала текстовый редактор под названием RiOI Editor. Редактор работает с ровно одним целым параметром $$$W$$$ — шириной каждой строки. Известно, что $$$1 \leq W \leq 10^5$$$.

Поскольку вы не можете понять язык RiOI, с вашей точки зрения слова отличаются друг от друга только своей длиной. Таким образом, статья длины $$$n$$$ определяется как последовательность $$$a$$$, состоящая из $$$n$$$ целых положительных чисел, где $$$a_i$$$ — длина $$$i$$$-го слова в статье. RiOI Editor отображает статью $$$[a_1, a_2,\ldots, a_n]$$$ на экране следующим образом:

  • Если $$$\max(a_1, a_2, \ldots, a_n) \gt W$$$, редактор не может отобразить статью;
  • В противном случае редактор может отобразить статью следующим образом:
    • Изначально $$$l = 1$$$, и $$$s = 0$$$. На протяжении всего процесса $$$l$$$ всегда обозначает текущее количество строк в редакторе, а $$$s$$$ всегда обозначает сумму длин слов в последней строке;
    • Затем, для каждого $$$1\le i\le n$$$:
      • Если $$$s + a_i \leq W$$$, слово вставляется в конец текущей строки. Таким образом, $$$l$$$ остается неизменным, а $$$s$$$ увеличивается на $$$a_i$$$.
      • В противном случае слово вставляется в новую строку. Таким образом, $$$l$$$ становится $$$l + 1$$$, а $$$s$$$ становится $$$a_i$$$.
    • Количество строк, необходимых для отображения статьи, равно конечному значению $$$l$$$.

Вам очень интересен редактор, поэтому вы решаете выяснить значение $$$W$$$, вводя некоторые статьи в редактор и наблюдая за количеством строк, необходимых для отображения каждой статьи.

Формально, вы можете задать жюри не более $$$2$$$ запросов. В каждом запросе вы вводите статью $$$[a_1, a_2, \ldots, a_n]$$$ ($$$1\leq n \leq 10^5$$$) в редактор, и жюри ответит вам:

  • Количество строк, необходимых для отображения статьи, если редактор может ее отобразить;
  • $$$0$$$, если редактор не может отобразить статью.
Входные данные

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

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

Для каждого набора входных данных вы можете сделать до $$$2$$$ запросов, чтобы выяснить значение $$$W$$$. Гарантируется, что $$$1\leq W\leq 10^5$$$.

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

  • $$$\texttt{? } n\texttt{ }a_1\texttt{ }a_2\texttt{ }\ldots\texttt{ }a_n$$$ ($$$1 \leq n, a_i \leq 10^5$$$) — статья, которую вы вводите в редактор.

В конце каждого запроса жюри напечатает целое число, как описано в условии.

Чтобы сообщить, что вы нашли значение $$$W$$$, напечатайте новую строку в следующем формате:

  • $$$\texttt{! } W$$$ — параметр редактора.

Печать ответа не считается одним из $$$2$$$ запросов.

После этого продолжайте обрабатывать следующий набор входных данных или завершите программу, если это был последний набор входных данных.

После вывода каждого запроса не забудьте вывести перевод строки и сбросить буфер вывода$$$^{\text{∗}}$$$. В противном случае вы получите вердикт Решение «зависло».

На любом шаге взаимодействия, если вы считали $$$-1$$$ вместо корректных данных, ваше решение должно немедленно завершиться. Это означает, что ваше решение получит вердикт Неправильный ответ из-за некорректного запроса или любой другой ошибки. Если программа не завершится, вы можете получить любой вердикт, так как ваша программа продолжит чтение из закрытого потока.

Взаимодействие в этой задаче является адаптивным. Это означает, что значение $$$W$$$ может изменяться в процессе взаимодействия, но гарантируется, что всегда существует хотя бы одно целое число $$$W$$$, удовлетворяющее всем запросам.

Взломы

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

Первая строка ввода содержит целое число $$$t$$$ ($$$1 \leq t \leq 10$$$) — количество наборов входных данных. Затем выведите строку «manual» в той же строке.

Единственная строка каждого набора входных данных содержит одно целое число $$$W$$$ ($$$1\le W\le 10^5$$$) — параметр редактора.

Формат взлома для примера выглядит следующим образом.

2 manual
20
1

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

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

2

1


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

? 5 1 9 4 6 1

? 2 10 10

! 20
? 1 2

! 1
Примечание

В первом наборе входных данных:

  • Для первого запроса общая длина слов составляет $$$1+9+4+6+1=21$$$, и статья отображается на двух строках, так что $$$W \lt 21$$$;
  • Для второго запроса общая длина слов составляет $$$10+10=20$$$, и статья отображается на одной строке, так что $$$W\ge 20$$$.

Таким образом, мы определили, что $$$W = 20$$$.

Во втором наборе входных данных редактор не может отобразить статью в единственном запросе. Значит, $$$W \lt 2$$$, так что оно может быть только $$$1$$$.