E. Удаление чисел
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Загадано неизвестное целое число $$$x$$$ ($$$1\le x\le n$$$). Вы хотите найти $$$x$$$.

Сначала у вас есть множество целых чисел $$$\{1, 2, \ldots, n\}$$$. Вы можете сделать следующие операции не более $$$10000$$$ раз:

  • A $$$a$$$: узнать, сколько есть чисел, делящихся на $$$a$$$ в текущем множестве.
  • B $$$a$$$: узнать, сколько есть чисел, делящихся на $$$a$$$ в текущем множестве и затем удалить все числа, делящиеся на $$$a$$$ из множества. При этом число $$$x$$$ не будет удаляться никогда (даже если оно делится на $$$a$$$). В этой операции $$$a$$$ должно быть больше $$$1$$$.
  • C $$$a$$$: вы делаете эту операцию, если вы знаете, что $$$x=a$$$. Эта операция может быть выполнена только один раз.

Обратите внимание, что в операции типа B должно выполняться, что $$$a>1$$$.

Напишите программу, которая найдет значение числа $$$x$$$.

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

В первой строке находится единственное целое число $$$n$$$ ($$$1\le n\le 10^5$$$). Остальные части входных данных будут получены в процессе взаимодействия.

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

Каждый раз, ваша программа должна вывести строку, содержащую один символ A, B или C и целое число $$$a$$$ ($$$1\le a\le n$$$ для операций A и C, $$$2\le a\le n$$$ для операций B). Эта строка описывает операцию, которую вы выполняете.

Если ваша операция имеет тип C, ваша программа должна завершиться немедленно.

Иначе ваша программа должна считать единственное целое число, являющееся ответом на вашу операцию.

После вывода каждой строки не забывайте сбрасывать буфер потока вывода. Для этого используйте:

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

Гарантируется, что число $$$x$$$ зафиксировано и не будет меняться в процессе взаимодействия.

Взломы:

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

В единственной строке находятся два целых числа $$$n$$$, $$$x$$$ ($$$1 \leq x \leq n \leq 10^5$$$).

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

2

4

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

B 4

A 2

A 8

C 4
Примечание

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

В первом тесте $$$n=10$$$ и $$$x=4$$$.

Изначальное множество — это $$$\{1,2,3,4,5,6,7,8,9,10\}$$$.

В первой операции вы спрашиваете, сколько чисел делятся на $$$4$$$ и удаляете их. Ответ $$$2$$$, потому что есть два числа, делящиеся на $$$4$$$: $$$\{4,8\}$$$. Число $$$8$$$ будет удалено, но $$$4$$$ нет, потому что число $$$x$$$ никогда не удаляется. Теперь множество — это $$$\{1,2,3,4,5,6,7,9,10\}$$$.

Во второй операции вы спрашиваете, сколько чисел являются делятся на $$$2$$$. Ответ равен $$$4$$$, потому что четыре числа делятся на $$$2$$$: $$$\{2,4,6,10\}$$$.

В третьей операции вы спрашиваете, сколько чисел делятся на $$$8$$$. Ответ равен $$$0$$$, потому что ни одно из чисел в текущем множестве не делится на $$$8$$$.

В четвертой операции вы сообщаете, что вы знаете, что $$$x=4$$$. Это является правильным ответом.