E. Докопаться до правды
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Nanatsukaze - Connect the World

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

Есть два скрытых целых числа $$$k$$$ и $$$c$$$, такие что $$$k\in \{1,2,3\}$$$ и $$$1\le c\le 2^n-1$$$. Обратите внимание, что $$$c\neq 0$$$.

До начала любых взаимодействий вам нужно сообщить жюри целое неотрицательное число $$$a\le 2^n-1$$$. Затем проверяющая система использует $$$a$$$ как начальный элемент множества $$$S$$$, то есть изначально $$$S = \{a\}$$$.

Далее вы можете сделать не более $$$n+3$$$ запросов следующих двух типов:

  1. Выбрать целое число $$$x$$$ такое, что $$$0\leq x\le 2^n-1$$$. Жюри добавит $$$f(x)$$$ в $$$S$$$, а затем ответит значением $$$|S|$$$ (то есть размером множества $$$S$$$ после добавления);
  2. Выбрать целое число $$$y$$$ такое, что $$$0\leq y\le 2^n-1$$$. Жюри ответит количеством целых чисел $$$z$$$, для которых выполнено $$$z\in S$$$ и $$$z\geq y$$$.

Функция $$$f(x)$$$ определяется следующим образом:

$$$$$$ f(x)= \begin{cases} x\,\&\,c & \text{if}\, k=1,\\ x\,|\,c & \text{if}\, k=2,\\ x\oplus c & \text{if}\, k=3.\\ \end{cases} $$$$$$

Здесь $$$\&$$$ обозначает операцию побитового И, $$$|$$$ обозначает операцию побитового ИЛИ, и $$$\oplus$$$ обозначает операцию побитового исключающего ИЛИ.

Ваша задача — определить значения $$$k$$$ и $$$c$$$, используя не более $$$n+3$$$ запросов.

Обратите внимание, что сообщение ответа не учитывается в $$$n+3$$$ взаимодействиях.

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \leq n \leq 60$$$). Затем следует взаимодействие.

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

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

Сначала вам нужно вывести целое число $$$a$$$ ($$$0\leq a\le 2^n-1$$$) — начальный элемент, который вы выбрали для множества $$$S$$$.

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

  1. $$$\mathtt{I}\;x$$$ ($$$0\leq x\le 2^n-1$$$)  — добавить $$$f(x)$$$ в множество $$$S$$$. После этого жюри вернёт $$$|S|$$$.
  2. $$$\mathtt{Q}\;y$$$ ($$$0\leq y\le 2^n-1$$$)  — запросить, сколько элементов $$$z$$$ в множестве $$$S$$$ удовлетворяют условию $$$z \geq y$$$. Жюри вернёт количество таких $$$z$$$.

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

  • $$$\mathtt{A}\;k\;c$$$ ($$$1\leq k\le 3$$$, $$$1\leq c\le 2^n-1$$$)  — значения $$$k$$$ и $$$c$$$.

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

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

Обратите внимание, что интерактор неадаптивен. Это означает, что значения $$$k$$$ и $$$c$$$ фиксируются в самом начале и не изменяются в зависимости от ваших запросов.

Взломы

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

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

Единственная строка каждого набора входных данных должна содержать три целых числа $$$n$$$, $$$k$$$ и $$$c$$$ ($$$2 \leq n \leq 60$$$, $$$1\leq k\le 3$$$, $$$1\leq c\le 2^n-1$$$).

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

$$$^{\text{∗}}$$$Чтобы сбросить буфер вывода, используйте:

  • fflush(stdout) или cout.flush() в C++;
  • sys.stdout.flush() в Python;
  • смотрите документацию для других языков.
Пример
Входные данные
3
2


1

2


2

1

2

2

3

2


2

2

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


3
I 3

A 1 3

1
I 0

Q 2

Q 1

Q 0

I 3

A 2 2

1
I 1

I 0

A 3 1
Примечание

Ниже показан процесс взаимодействия в примере:

РешениеЖюриПояснение
3Есть $$$3$$$ набора входных данных.
2$$$n=2$$$. Скрытые значения равны $$$k=1$$$ и $$$c=3$$$.
3Изначально $$$S = \{3\}$$$.
I 31Добавляется $$$f(3)=3\,\& \,3=3$$$ в $$$S$$$. Тогда $$$S=\{3\}$$$, поэтому ответ равен $$$|S|=1$$$. Обратите внимание, что элементы множества $$$S$$$ не могут повторяться.
A 1 3Решение делает вывод, что $$$k=1$$$ и $$$c=3$$$.
2$$$n=2$$$. Скрытые значения равны $$$k=2$$$ и $$$c=2$$$.
1Изначально $$$S = \{1\}$$$.
I 02Добавляется $$$f(0)=0\,|\,2=2$$$ в $$$S$$$. Тогда $$$S=\{1,2\}$$$, поэтому ответ равен $$$|S|=2$$$.
Q 21При $$$z$$$ равном $$$2$$$ выполняется $$$z\in S$$$ и $$$z\geq 2$$$, поэтому ответ равен $$$1$$$.
Q 12При $$$z$$$ равном $$$1$$$ или $$$2$$$ выполняется $$$z\in S$$$ и $$$z\geq 1$$$, поэтому ответ равен $$$2$$$.
Q 02При $$$z$$$ равном $$$1$$$ или $$$2$$$ выполняется $$$z\in S$$$ и $$$z\geq 0$$$, поэтому ответ равен $$$2$$$.
I 33Добавляется $$$f(3)=3\,|\,2=3$$$ в $$$S$$$. Тогда $$$S=\{1,2,3\}$$$, поэтому ответ равен $$$|S|=3$$$.
A 2 2Решение делает вывод, что $$$k=2$$$ и $$$c=2$$$.
2$$$n=2$$$. Скрытые значения равны $$$k=3$$$ и $$$c=1$$$.
1Изначально $$$S = \{1\}$$$.
I 12Добавляется $$$f(1)=1\oplus 1=0$$$ в $$$S$$$. Тогда $$$S=\{0,1\}$$$, поэтому ответ равен $$$|S|=2$$$.
I 02Добавляется $$$f(1)=0\oplus 1=1$$$ в $$$S$$$. Тогда $$$S=\{0,1\}$$$, поэтому ответ равен $$$|S|=2$$$. Обратите внимание, что элементы множества $$$S$$$ не могут повторяться.
A 3 1Решение делает вывод, что $$$k=3$$$ и $$$c=1$$$.

Пустые строки во входных и выходных данных примера приведены только для лучшей читаемости; в вашей программе выводить их не нужно.

Обратите внимание, что в примере приведённых запросов на самом деле недостаточно, чтобы однозначно определить значения; они даны только для иллюстрации формата ввода/вывода.