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

Вам дан массив $$$x_1, \ldots, x_n$$$ из чисел от $$$1$$$ до $$$n$$$. Также у жюри есть заранее фиксированный, но скрытый от вас массив $$$y_1, \ldots, y_n$$$ из чисел от $$$1$$$ до $$$n$$$. Элементы массива $$$y$$$ вам неизвестны. Дополнительно известно, что для всех $$$i$$$ выполнено $$$x_i \neq y_i$$$, а также все пары $$$(x_i, y_i)$$$ различны.

Жюри загадало один из двух объектов, вам нужно угадать, какой именно:

• Объект A: Ориентированный граф на $$$n$$$ вершинах с номерами от $$$1$$$ до $$$n$$$, и с $$$n$$$ рёбрами вида $$$x_i \to y_i$$$.
• Объект B: $$$n$$$ точек на координатной плоскости. $$$i$$$-я точка имеет координаты $$$(x_i, y_i)$$$.

Чтобы отгадать, какой объект загадало жюри, вы можете делать запросы. В одном запросе вы должны задать два числа $$$i, j$$$ $$$(1 \leq i, j \leq n, i \neq j)$$$. В ответ вам будет возвращено одно число:

• Если жюри загадало Объект A, вам вернут длину кратчайшего пути (в рёбрах) от вершины $$$i$$$ до вершины $$$j$$$ в графе, или же $$$0$$$, если пути нет.
• Если жюри загадало Объект B, вам вернут Манхэттенское расстояние между точками $$$i$$$ и $$$j$$$, то есть: $$$|x_i -x_j| + |y_i - y_j|$$$

У вас есть $$$2$$$ запроса, чтобы определить, какой из объектов загадало жюри.

Взаимодействие начинается со считывания $$$n$$$ ($$$3 \leq n \leq 2 \cdot 10^5$$$) — длина массива $$$x$$$ и $$$y$$$, в начале каждого набора входных данных.

Далее, в следующей строке считайте $$$n$$$ целых чисел: $$$x_1, x_2, \ldots, x_n$$$ ($$$1 \leq x_i \leq n$$$) — элементы массива $$$x$$$.

Массив $$$y_1, y_2, \ldots, y_n$$$ фиксирован для каждого теста. Иными словами, интерактор не адаптивен.

Гарантируется, что $$$x_i \neq y_i$$$ для всех $$$1 \leq i \leq n$$$, а также все пары $$$(x_i, y_i)$$$ различны.

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

Чтобы задать запрос, выведите «? $$$i$$$ $$$j$$$» (без кавычек, $$$1 \le i, j \le n, i \neq j$$$). Затем вы должны считать ответ на запрос, который является целым неотрицательным числом.

Чтобы дать ответ, выведите «! A», если загадан Объект A или «! B» если загадан Объект B (вывод без кавычек). Заметьте, что вывод ответа не считается одним из $$$2$$$ запросов.

После вывода каждого запроса не забудьте вывести перевод строки и сбросить буфер вывода$$$^{\text{∗}}$$$. В противном случае вы получите вердикт Решение «зависло». На любом шаге взаимодействия, если вы считали $$$-1$$$ вместо корректных данных, ваше решение должно немедленно завершиться. Это означает, что ваше решение получит вердикт Неправильный ответ из-за некорректного запроса или любой другой ошибки. Если программа не завершится, вы можете получить любой вердикт, так как ваша программа продолжит чтение из закрытого потока. Обратите внимание, что если запрос корректный, ответ на него никогда не будет равен $$$-1$$$.

Взломы

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

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

Вторая строка каждого набора должна содержать $$$n$$$ целых чисел — $$$x_1, x_2, \ldots, x_n$$$ ($$$1 \le x_i \le n$$$).

Третья строка каждого набора должна содержать $$$n$$$ целых чисел — $$$y_1, y_2, \ldots, y_n$$$ ($$$1 \le y_i \le n$$$).

Необходимо, чтобы $$$x_i \neq y_i$$$ для всех $$$1 \le i \le n$$$, а также все пары $$$(x_i, y_i)$$$ должны быть различны.

В четвёртой строке должен содержаться один символ: A или B, обозначающий, какой из объектов вы хотите загадать.

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