A. Побитовая магия
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Загадана секретная последовательность $$$p_0, p_1, \ldots, p_{n-1}$$$, являющаяся перестановкой чисел $$$\{0,1,\ldots,n-1\}$$$.

Вам нужно найти два индекса $$$i$$$ и $$$j$$$, таких что $$$p_i \oplus p_j$$$ принимает максимальное значение, где $$$\oplus$$$ обозначает операцию побитового исключающего ИЛИ.

Чтобы их найти, вы можете делать запросы. Каждый запрос устроен так: вы выбираете произвольные индексы $$$a$$$, $$$b$$$, $$$c$$$ и $$$d$$$ ($$$0 \le a,b,c,d < n$$$). Затем программа жюри вычисляет $$$x = (p_a \mid p_b)$$$ и $$$y = (p_c \mid p_d)$$$, где $$$|$$$ обозначает операцию побитового ИЛИ. Наконец, вы узнаёте результат сравнения чисел $$$x$$$ и $$$y$$$. Другими словами, вам сообщают, какое из трёх условий выполнено: $$$x < y$$$, $$$x > y$$$ или $$$x = y$$$.

Найдите два индекса $$$i$$$ и $$$j$$$ ($$$0 \le i,j < n$$$), таких что $$$p_i \oplus p_j$$$ максимально среди всех таких пар, сделав не более $$$3n$$$ запросов. Если существует несколько пар индексов, удовлетворяющих условию, выведите любую из них.

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

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

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

Первая строка каждого набора входных данных содержит единственное число $$$n$$$ ($$$2 \le n \le 10^4$$$). В этот момент загадывается перестановка $$$p_0, p_1, \ldots, p_{n-1}$$$. В этой задаче решение жюри неадаптивно. Иначе говоря, последовательность $$$p$$$ фиксирована в каждом наборе входных данных и не будет меняться в процессе взаимодействия с программой участника.

Чтобы сделать запрос, вам нужно выбрать четыре индекса $$$a$$$, $$$b$$$, $$$c$$$ и $$$d$$$ ($$$0 \le a,b,c,d < n$$$) и вывести строку следующего вида:

  • «? a b c d»

После этого вы получите:

  • «<», если $$$(p_a \mid p_b) < (p_c \mid p_d)$$$;
  • «=», если $$$(p_a \mid p_b) = (p_c \mid p_d)$$$;
  • «>», если $$$(p_a \mid p_b) > (p_c \mid p_d)$$$.

Вы можете сделать не более $$$3n$$$ запросов такого вида.

Затем, если ваша программа нашла пару индексов $$$i$$$ и $$$j$$$ ($$$0 \le i, j < n$$$), такую что $$$p_i \oplus p_j$$$ максимально, выведите строку следующего вида:

  • «! i j»

Обратите внимание, что эта строка не считается запросом и не учитывается при подсчёте числа сделанных запросов.

После этого переходите к обработке следующего набора входных данных.

Если вы делаете больше $$$3n$$$ запросов, ваша программа должна немедленно завершиться, в таком случае вы получите вердикт Wrong Answer. В противном случае вы можете получить произвольный вердикт, поскольку ваше решение продолжит читать из закрытого потока данных.

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

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

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

Взломы

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

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

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

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$p_0,p_1,\ldots,p_{n-1}$$$, которые задают перестановку чисел от $$$0$$$ до $$$n - 1$$$.

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

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

<

=

>

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


? 0 2 3 1

? 1 1 2 3

? 1 2 0 3

! 3 2

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

В первом наборе входных данных загадана перестановка $$$p=[0,3,1,2]$$$.

На запрос «? 0 2 3 1» решение жюри выведет «<», поскольку $$$(p_0 \mid p_2) = (0 \mid 1) =1 < (p_3 \mid p_1) = (2 \mid 3) = 3$$$.

На запрос «? 1 1 2 3» решение жюри выведет «=», поскольку $$$(p_1 \mid p_1) = (3\mid 3)= 3 = (p_2 \mid p_3) = (1 \mid 2)=3$$$.

На запрос «? 1 2 0 3» решение жюри выведет «>», поскольку $$$(p_1 \mid p_2) = (3 \mid 1) = 3 > (p_0 \mid p_3) = (0\mid 2)=2$$$.

Ответ $$$i = 3$$$ и $$$j = 2$$$ корректен: $$$(p_3 \oplus p_2) = (2 \oplus 1) = 3$$$, и это значение максимально среди всех пар $$$p_i \oplus p_j$$$. Другим корректным ответом также является пара $$$i=0$$$ и $$$j=1$$$. Поскольку число запросов не превысило $$$3n=12$$$, ответ считается верным.

Во втором наборе входных данных $$$n = 2$$$, значит, $$$p$$$ есть либо $$$[0, 1]$$$, либо $$$[1, 0]$$$. В любом случае $$$p_0 \oplus p_1 = 1$$$ максимально возможно.