F. Рудольф и мимик
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Рудольф — ученый, изучающий инопланетную форму жизни. Перед Рудольфом находится комната, в которой раскидано $$$n$$$ различных объектов. Среди объектов есть ровно одно поразительное существо — мимик, умеющий превращаться в любой объект. Он уже замаскировался в этой комнате и Рудольфу нужно найти его при помощи эксперимента.

Эксперимент проходит в несколько этапов. На каждом этапе происходит следующее:

  • Сначала Рудольф осматривает все объекты в комнате и записывает их типы. Тип каждого объекта обозначается цифрой, может быть несколько объектов одного типа.
  • После осмотра Рудольф может указать на объект, который по его мнению является мимиком. После этого эксперимент завершается. У Рудольфа есть только одна попытка, поэтому, если он не уверен в положении мимика, он вместо этого выполняет следующий пункт.
  • Рудольф может убрать любое количество объектов из комнаты(возможно ноль). Затем Рудольф выходит из комнаты и в это время все объекты, включая мимика, перемешиваются между собой, меняется их порядок, а мимик может превратиться в любой другой объект(даже в тот, которого нет в комнате).
  • После этого Рудольф возвращается в комнату и повторяет этап. Мимик может не изменять свой вид, но он не может оставаться тем же объектом больше двух этапов подряд.

Задача Рудольфа обнаружить мимика не более чем за пять этапов.

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ $$$(2 \le n \le 200)$$$ — количество объектов в комнате.

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

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

После того, как вы считали описание набора входных данных, вы должны сделать не более чем $$$5$$$ запросов. Считывание входных данных считается началом первого этапа, и мимик уже может начать изменяться.

Запрос является строкой. Первый символ строки означает тип запроса. Чтобы удалить объекты, выведите символ «-». После этого выведите число $$$k$$$ — сколько объектов вы хотите убрать. После идут $$$k$$$ чисел — номера объектов в их текущем расположении. Индексация начинается с единицы. Вы можете удалить мимика, но в таком случае вы не сможете указать на него и получите вердикт «Неправильный ответ».

В ответ на запрос придет строка, содержащая целые числа — оставшиеся в комнате объекты после удаления и перемешивания.

Чтобы указать положение мимика выведите символ «!», после этого выведите номер объекта, который является мимиком.

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

Если вы сделаете больше пяти запросов или сделаете некорректный запрос, решение получит вердикт «Неправильный ответ».

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

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

Взломы

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

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

Первая строка каждого набора содержит два целых числа $$$n$$$, $$$k$$$ ($$$2 \le n \le 200, 1 \le k \le n$$$) — количество объектов и позиция мимика.

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

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

2 1 1 2

2 2 2

2

8
1 2 3 4 3 4 2 1

4 3 4 3 2 2 1 3
 
2 3 3 2

5 3 2

2 5

15
1 2 3 4 5 6 7 8 7 6 5 4 3 2 1 

1 2 3 4 5 6 7 8 7 9 5 4 3 2 1
Выходные данные
 
 
- 1 5

- 1 3

- 2 1 2

! 1


- 0

- 4 1 3 7 8

- 1 4

- 1 2

! 2


- 0

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

Пояснение к первому тесту: изначальный массив $$$x_1$$$, $$$x_2$$$, $$$x_3$$$, $$$x_4$$$, $$$x_5$$$. Мимик находится на первой позиции.

  • Удаляем пятый объект. После этого позиция перемешиваются, и мимик выбрал не менять свой вид. Позиции объектов становятся $$$x_4$$$, $$$x_1$$$, $$$x_2$$$, $$$x_3$$$.
  • Удаляем третий объект. Мимик вынужден превратится в другой объект, потому что он уже два этапа находился в виде $$$1$$$. Мимик выбрал превратиться в $$$2$$$, объекты перемешиваются и становятся $$$x_3$$$, $$$x_4$$$, $$$x_1$$$.
  • Удаляем первый и второй объекты. Позиции объектов становятся $$$x_1$$$. Остается только мимик, и он остается объектом $$$2$$$.
  • Указываем на первый объект.