D1. Ассасин (простая версия)
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

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

На сборах сборной Мексики к IOI существует традиция играть в игру «Ассасин», которая похожа на «Among Us» или «Мафию».

Сегодня $$$n$$$ игроков, пронумерованных от $$$1$$$ до $$$n$$$, будут играть в «Ассасин» со следующими тремя ролями:

  • Рыцарь: Рыцарь — это тот, кто всегда говорит правду.
  • Лжец: Лжец — это тот, кто всегда лжет.
  • Предатель: Предатель — это тот, кого все считают Рыцарем, а на самом деле он Лжец.

Каждому игроку будет назначена своя роль в игре. В игре будет ровно один Предатель, но может быть любое (возможно нулевое) количество Рыцарей и Лжецов.

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

Чтобы определить Предателя, вы зададите несколько вопросов. В каждом вопросе вы выбираете двух игроков $$$i$$$ и $$$j$$$ ($$$1 \leq i, j \leq n$$$; $$$i \neq j$$$) и спрашиваете, считает ли игрок $$$i$$$, что игрок $$$j$$$ — Рыцарь. Результаты этого вопроса приведены в таблице ниже.

РыцарьЛжецПредатель
РыцарьДаНетДа
ЛжецНетДаНет
ПредательНетДа
Значение ячейки в строке $$$a$$$ и столбце $$$b$$$ — это ответ на вопрос, когда $$$i$$$ имеет роль $$$a$$$, а $$$j$$$ — роль $$$b$$$. Например, «Да» в правой верхней ячейке принадлежит строке «Рыцарь» и столбцу «Предатель», поэтому это ответ на вопрос, когда $$$i$$$ — Рыцарь, а $$$j$$$ — Предатель.

Найдите Предателя не более чем за $$$n + 69$$$ вопросов.

Заметьте, что итерактор адаптивен: роли игроков не фиксированы изначально и могут меняться в зависимости от ваших вопросов. Однако гарантируется, что существует такое распределение ролей, которое соответствует всем ранее заданным вопросам в ограничениях этой задачи.

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$3 \le n \le 10^5$$$) — количество людей, играющих в игру.

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

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

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

  • «? i j» ($$$1 \leq i,j \leq n$$$; $$$i \neq j$$$) — спросить игрока $$$i$$$, считает ли он игрока $$$j$$$ Рыцарем.

Жюри выдаст «1», если игрок $$$i$$$ считает игрока $$$j$$$ Рыцарем, и «0» в противном случае.

Когда вы определите, какой игрок является Предателем, выведите строку в следующем формате:

  • «! i» ($$$1 \leq i \leq n$$$) — Предателем является игрок $$$i$$$.

Обратите внимание, что ответы не учитываются в ограничении в $$$n+69$$$ вопросов.

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

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

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

Формат взломов

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

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

Первая строка каждого набора входных данных должна содержать целое число $$$n$$$, за которым следует строка «manual».

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$-1 \le a_i \le 1$$$) — роли каждого игрока. $$$1$$$ обозначает Рыцаря, $$$0$$$ — Лжеца, а $$$-1$$$ — Предателя. Предатель должен быть ровно один, то есть должен быть ровно один индекс $$$i$$$ такой, что $$$a_i=-1$$$.

В качестве примера приводим взлом, аналогичный примеру из условия:

2
7 manual
0 1 0 -1 0 1 0
4 manual
0 1 -1 0
Пример
Входные данные
2
7

1

0

0

1

1

0

0

1

4

0

1

1

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


? 1 3

? 7 6

? 2 5

? 6 2

? 4 5

? 4 6

? 1 4

? 2 4

! 4

? 1 2

? 2 3

? 3 4

? 4 1

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

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

В первом наборе входных данных игроки с индексами $$$2$$$ и $$$6$$$ — Рыцари, игроки с индексами $$$1$$$, $$$3$$$, $$$5$$$ и $$$7$$$ — Лжецы, а Предатель имеет индекс $$$4$$$. Ниже приводится объяснение заданных вопросов:

  • В первом вопросе игрок $$$i$$$ является Лжецом, и игрок $$$j$$$ также Лжец. Ответ — «да», так как Лжецы всегда лгут.
  • Во втором вопросе игрок $$$i$$$ — Лжец, а игрок $$$j$$$ — Рыцарь. Ответ — «нет», так как Лжецы всегда лгут.
  • В третьем вопросе игрок $$$i$$$ — Рыцарь, а игрок $$$j$$$ — Лжец. Ответ — «нет», так как Рыцари всегда говорят правду.
  • В четвертом вопросе игрок $$$i$$$ — Рыцарь, и игрок $$$j$$$ также Рыцарь. Ответ — «да», так как Рыцари всегда говорят правду.
  • В пятом вопросе игрок $$$i$$$ — Предатель, а игрок $$$j$$$ — Лжец. Ответ — «да», так как Предатель всегда лжет.
  • В шестом вопросе игрок $$$i$$$ — Предатель, а игрок $$$j$$$ — Рыцарь. Ответ — «нет», так как Предатель всегда лжет.
  • В седьмом вопросе игрок $$$i$$$ — Лжец, а игрок $$$j$$$ — Предатель. Ответ — «нет», так как Лжецы всегда лгут, и Лжецы думают, что Предатель является Рыцарем.
  • В восьмом вопросе игрок $$$i$$$ — Рыцарь, а игрок $$$j$$$ — Предатель. Ответ — «да», так как Рыцари всегда говорят правду, и Рыцари думают, что Предатель является Рыцарем.