Deleting Numbers
Contest: Codeforces Round 670 (Div. 2)
Difficulty rating: 2600
Tags: interactive, math, number theory

This is an interactive problem.

There is an unknown integer $$$x$$$ ($$$1\le x\le n$$$). You want to find $$$x$$$.

At first, you have a set of integers $$$\{1, 2, \ldots, n\}$$$. You can perform the following operations no more than $$$10000$$$ times:

- A $$$a$$$: find how many numbers are multiples of $$$a$$$ in the current set.
- B $$$a$$$: find how many numbers are multiples of $$$a$$$ in this set, and then delete all multiples of $$$a$$$, but $$$x$$$ will never be deleted (even if it is a multiple of $$$a$$$). In this operation, $$$a$$$ must be greater than $$$1$$$.
- C $$$a$$$: it means that you know that $$$x=a$$$. This operation can be only performed once.

Remember that in the operation of type B $$$a>1$$$ must hold.

Write a program, that will find the value of $$$x$$$.

Input format:
The first line contains one integer $$$n$$$ ($$$1\le n\le 10^5$$$). The remaining parts of the input will be given throughout the interaction process.

Interaction format:
In each round, your program needs to print a line containing one uppercase letter A, B or C and an integer $$$a$$$ ($$$1\le a\le n$$$ for operations A and C, $$$2\le a\le n$$$ for operation B). This line desribes operation you make.

If your operation has type C your program should terminate immediately.

Else your program should read one line containing a single integer, which is the answer to your operation.

After outputting each line, don't forget to flush the output. To do it use:

- fflush(stdout) in C/C++;
- System.out.flush() in Java;
- sys.stdout.flush() in Python;
- flush(output) in Pascal;
- See the documentation for other languages.

It is guaranteed, that the number $$$x$$$ is fixed and won't change during the interaction process.

Hacks:

To make a hack, use such input format:

The only line should contain two integers $$$n$$$, $$$x$$$ ($$$1 \leq x \leq n \leq 10^5$$$).

Constraints:
Time limit: 1.0 s
Memory limit: 512.0 MB

Note:
Note that to make the sample more clear, we added extra empty lines. You shouldn't print any extra empty lines during the interaction process.

In the first test $$$n=10$$$ and $$$x=4$$$.

Initially the set is: $$$\{1,2,3,4,5,6,7,8,9,10\}$$$.

In the first operation, you ask how many numbers are multiples of $$$4$$$ and delete them. The answer is $$$2$$$ because there are two numbers divisible by $$$4$$$: $$$\{4,8\}$$$. $$$8$$$ will be deleted but $$$4$$$ won't, because the number $$$x$$$ will never be deleted. Now the set is $$$\{1,2,3,4,5,6,7,9,10\}$$$.

In the second operation, you ask how many numbers are multiples of $$$2$$$. The answer is $$$4$$$ because there are four numbers divisible by $$$2$$$: $$$\{2,4,6,10\}$$$.

In the third operation, you ask how many numbers are multiples of $$$8$$$. The answer is $$$0$$$ because there isn't any number divisible by $$$8$$$ in the current set.

In the fourth operation, you know that $$$x=4$$$, which is the right answer.

Example input:
10

2

4

0

Example output:
B 4

A 2

A 8

C 4

Editorial:
If we know what prime factors x has, we can find $$$x$$$ just using bruteforce.
To find the prime factors, we can just do $$$B~p$$$ for every prime $$$p$$$ in ascending order, meanwhile calculate the numbers there supposed to be without $$$x$$$, if it differs with the number the interactor gives, then $$$x$$$ contains the prime factor $$$p$$$.
This way, we can find every prime factor except for the smallest one.
Let $$$m$$$ be the number of primes no greater than $$$n$$$.
Then we can split the prime numbers into $$$\sqrt m$$$ groups.
After finishing asking a group, ask $$$A~1$$$ and check if the return value same as it supposed to be without $$$x$$$. If it's the first time finding it different, it means the smallest prime number is in the range, then just check every prime numbers in the range by asking $$$A~p$$$.
After finding the prime factors, for each factor, ask $$$A~p^k$$$, it can be proved this step will be done around $$$\log(n)$$$ times.
The total number of operations if around $$$m+2\sqrt m+\log(n)$$$, the total time complexity is $$$O(n\log n)$$$