Это интерактивная задача с двойным запуском.

Есть два игрока: игрок A и игрок B. Жюри (также в этой задачи называемое интерактором) сначала взаимодействует с игроком A. После завершения взаимодействия с игроком A жюри взаимодействует с игроком B. Обратите внимание, что игроки A и игрок B не могут напрямую передавать информацию друг другу; оба игрока могут только отправлять информацию или получать информацию от жюри.

Перед взаимодействием жюри определяет целое число $$$n$$$ и перестановку $$$p$$$$$$^{\text{∗}}$$$ целых чисел от $$$1$$$ до $$$n$$$ ровно один раз. Эти значения одинаковы для обоих игроков.

Игрок A получает значение $$$n$$$ и все элементы $$$p$$$ от жюри. Затем Игрок A должен отправить бинарное целое число $$$x$$$ (то есть $$$x$$$ должно быть равно $$$0$$$ или $$$1$$$) обратно жюри.

Игрок B получает значение $$$n$$$ и целое число $$$x$$$ (то же самое целое число, которое отправил игрок A) от жюри. Однако перестановка $$$p$$$ не предоставляется игроку B. Задача игрока B состоит в том, чтобы определить позицию целого числа $$$n$$$ в $$$p$$$. Для этого игрок B может задать жюри не более $$$30$$$ запросов в следующей форме:

• Выберите любые два целых числа $$$l$$$ и $$$r$$$ ($$$l \leq r$$$), и жюри ответит значением $$$\max(p_{l}, p_{l+1}, \ldots, p_{r}) - \min(p_{l}, p_{l+1}, \ldots, p_{r})$$$.

Игрок A хочет убедиться, что игрок B сможет определить позицию $$$n$$$. Ваша задача состоит в том, чтобы действовать как оба игрока и определить оптимальную стратегию взаимодействия для обоих игроков, чтобы игрок B правильно определил позицию $$$n$$$.

Первый запуск

Ваш код будет выполняться ровно дважды для каждого теста. При первом запуске вы будете игроком A.

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

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

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

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

Вторая строка $$$i$$$-го набора входных данных содержит $$$n$$$ целых чисел, разделённых пробелами $$$p_1, p_2, \ldots, p_n$$$. Гарантируется, что эта последовательность образует перестановку.

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

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

Для каждого набора входных данных выведите целое число $$$x$$$, либо $$$0$$$, либо $$$1$$$, в новой строке. Это целое число будет отправлено вам при втором запуске.

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

Второй запуск

При втором запуске вы будете игроком B.

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

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

Вторая строка входных данных содержит ровно одно целое число $$$t$$$ — количество наборов входных данных ($$$1 \le t \le 100$$$). Обратите внимание, что это число равно $$$t$$$ из входных данных первого запуска.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$x$$$ ($$$2 \leq n \leq 10^4$$$, $$$0 \leq x \leq 1$$$). Это обозначает длину $$$p$$$ и бинарное целое число $$$x$$$, которое было отправлено Игроком A из последнего запуска.

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

Взаимодействие

Для $$$i$$$-го набора входных данных вы сначала получите $$$n$$$ и $$$x$$$ во входных данных от жюри в соответствии с форматом входных данных выше. После получения этих входных данных вы сможете сделать не более $$$30$$$ запросов следующего вида:

• ? l r ($$$1 \leq l \leq r \leq n$$$).

После каждого запроса жюри ответит значением $$$\max(p_{l}, p_{l+1}, \ldots, p_{r}) - \min(p_{l}, p_{l+1}, \ldots, p_{r})$$$, которое вы должны прочитать из потока входных данных.

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

Когда вы будете готовы сообщить позицию $$$n$$$, вы можете сделать это в следующем формате:

• ! P ($$$1 \leq P \leq n$$$), где $$$P$$$ — это позиция $$$n$$$.

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

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

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

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