E. Мешки с монетами 6-7
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Але и София хотят побеждать в каждой битве аур в городе, поэтому готовят уличный фокус с мешками монет.

На столе стоят $$$n$$$ мешков. В $$$i$$$-м мешке находится $$$a_i$$$ монет. В каждом мешке все монеты относятся к одному типу: либо это монеты типа $$$6$$$, каждая из которых весит $$$6$$$ граммов, либо монеты типа $$$7$$$, каждая из которых весит $$$7$$$ граммов. Ровно в одном мешке находятся монеты типа $$$6$$$, а в остальных $$$n - 1$$$ мешках — монеты типа $$$7$$$. Але и София знают массив $$$a$$$, но не знают, в каком мешке находятся монеты типа $$$6$$$.

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

Пусть $$$f(a)$$$ — минимальное количество запросов, достаточное, чтобы гарантированно найти мешок с монетами типа $$$6$$$ независимо от того, какой это мешок. Помогите Але и Софии найти этот мешок, использовав не более $$$f(a)$$$ запросов.

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

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

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

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

Во второй строке каждого набора входных данных содержатся $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — количество монет в каждом мешке.

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

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

Для каждого набора входных данных сначала считайте $$$n$$$ и массив $$$a$$$. После этого можно делать запросы.

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

  • ? $$$b_1\; b_2\; \ldots\; b_n$$$ ($$$0 \le b_i \le a_i$$$) — здесь $$$b_i$$$ — количество монет, выбранных из $$$i$$$-го мешка.

После каждого запроса считайте одно целое число — общий вес выбранных монет, $$$\sum_{i=1}^{n} b_i \cdot w_i$$$, где $$$w_i = 6$$$, если в $$$i$$$-м мешке находятся монеты типа $$$6$$$, и $$$w_i = 7$$$ в противном случае. Этот вес может не помещаться в $$$32$$$-битный целочисленный тип.

Определив мешок с монетами типа $$$6$$$, выведите строку следующего формата:

  • ! $$$i$$$ ($$$1 \le i \le n$$$) — здесь $$$i$$$ — индекс мешка с монетами типа $$$6$$$.
Эта строка не учитывается в ограничении на $$$f(a)$$$ запросов. После правильного ответа перейдите к следующему набору входных данных или завершите программу, если это был последний набор. После правильного ответа интерактор не отправляет подтверждающее значение.

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

После вывода запроса или ответа выведите перевод строки и очистите буфер вывода. В противном случае вы можете получить вердикт «Превышено время бездействия». Чтобы очистить буфер вывода, используйте:

  • fflush(stdout) или cout.flush() в C++;
  • System.out.flush() в Java;
  • sys.stdout.flush() в Python;
  • std::io::stdout().flush() в Rust;
  • для других языков смотрите документацию.

Взломы

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

Первая строка должна содержать число наборов входных данных $$$(1 \le t \le 5000)$$$. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных должна содержать целое число $$$n$$$ ($$$2 \le n \le 10^5$$$) — количество мешков — затем строку manual, затем целое число $$$k$$$ ($$$1 \le k \le n$$$) — индекс мешка с монетами по $$$6$$$ граммов.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — количество монет в каждом мешке.

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

Пример
Входные данные
2
5
1 1 2 2 2

34

33

4
3 2 4 3

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



? 1 0 1 2 1

? 1 1 2 0 1

! 3


? 3 2 2 0

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

Пример взаимодействия не соответствует оптимальной стратегии и приведён лишь для демонстрации формата ввода и вывода.

Дополнительные пустые строки в примере добавлены только для удобства чтения и не являются частью фактического ввода или вывода.

В первом наборе входных данных $$$n = 5$$$ и $$$a = [1, 1, 2, 2, 2]$$$. Монеты типа $$$6$$$ находятся в третьем мешке. Показанные значения веса вычисляются следующим образом:

  • ? 1 0 1 2 1: выбрано пять монет, причём $$$b_3 = 1$$$, поэтому получаем $$$7 \cdot (1 + 0 + 2 + 1) + 6 \cdot 1 = 34$$$.
  • ? 1 1 2 0 1: выбрано пять монет, причём $$$b_3 = 2$$$, поэтому получаем $$$7 \cdot (1 + 1 + 0 + 1) + 6 \cdot 2 = 33$$$.
Затем участник выводит ! 3, указывая третий мешок.

Во втором наборе входных данных $$$n = 4$$$ и $$$a = [3, 2, 4, 3]$$$. Монеты типа $$$6$$$ находятся во втором мешке. Запрос ? 3 2 2 0 выбирает семь монет, в том числе две из второго мешка, поэтому ответ равен $$$7 \cdot (3 + 2 + 0) + 6 \cdot 2 = 47$$$.

Затем участник выводит ! 2. Этот ответ верен для показанного выбора скрытого мешка, но запрос не позволяет различить второй и третий мешки.