Problem B
Going to Seed

The Great Seedling is a mythical spirit that supposedly rewards whoever catches it with farm crops that remain in bloom forever. Rumor has it that in the dead of tonight, it will be coming to Sweet Apple Acres—the Apple family’s farm!

Figure 1: Illustration by Kyle Coate.

Applejack and Apple Bloom are hoping to catch the Great Seedling to help out with their massive harvest this season. They’ve decided to stake out the farm and keep close watch over the trees; they’re going to see if they can sense the Great Seedling’s movements. Now, catching the Great Seedling is no easy feat, and they’ve only got one shot—if the Great Seedling becomes aware that it’s being hunted, it will flee and will never be found again!

There are $N$ trees in Sweet Apple Acres, laid out in a row and labelled $1, 2, \dots , N$ from left to right. The Great Seedling is hiding behind one of these trees, but they do not know which one.

In one half-hour, Applejack and Apple Bloom can each choose a consecutive range of trees, and they will intently observe that range of trees. The Great Seedling is restless and so sometime within this half-hour, it may spring from its current tree to an adjacent one. It does this very sneakily, but as it lands it will cause the leaves of the new tree, and only this tree, to rustle. If the Great Seedling does not spring to a new tree, he will move within the same tree and the leaves will rustle.

At the end of the half-hour, Applejack and Apple Bloom will then each report whether they sensed a rustle among the leaves of the trees they were intently observing. Unfortunately, because the Great Seedling’s movement is very subtle, they won’t be able to determine exactly which tree’s leaves rustled; however, we can assume that they are paying close enough attention that they will never make a mistake.

Once they are sure which tree the Great Seedling is in, they can quickly rush there to capture it; the Great Seedling will not have time to react. However, they only have one attempt—because they will be making a lot of noise, if they choose the wrong tree, the Great Seedling will flee, and all will be for naught.

There are only $32$ half-hours before the sun rises again and the Great Seedling leaves for good. This is their one chance. Help them catch the Great Seedling!

Interaction

First, your program should read a single integer $N$ ($2 \leq N \leq 10^9$), the number of trees, on a single line from standard input.

Then, we repeat the following process:

• Your program writes a single line to the standard output in either format:

  • $\texttt{Q}\: l_1\: r_1\: l_2\: r_2$ ($1 \leq l_1 \leq r_1 \leq N$; $1 \leq l_2 \leq r_2 \leq N$), meaning that for the next half-hour, Applejack should observe all the trees with labels from $l_1$ to $r_1$, inclusive, and Applebloom should observe the trees with labels from $l_2$ to $r_2$, inclusive. Note that these ranges can overlap, and in particular they can even be the same range. This can be done at most $32$ times.

  • $\texttt{A}\: t$ ($1 \leq t \leq N$), meaning that you are sure that the Great Seedling is in tree $t$ and they should rush to capture it immediately.

• If your program asks a question, your program should read two integers $w_1$ and $w_2$ ($0 \leq w_1, w_2 \leq 1$) from standard input. If $w_1 = 0$, it means Applejack did not sense a rustle; if $w_1 = 1$, it means she did. Similarly, if $w_2 = 0$, it means Apple Bloom did not sense a rustle; if $w_2 = 1$, it means she did.

• If your program guesses the answer, your answer will be checked. Your program should terminate immediately after this.

After asking each question, do not forget to output end of line and flush the output. To do this, use:

• fflush(stdout) or cout.flush() in C++;

• System.out.flush() in Java;

• stdout.flush() in Python;

• see documentation for other languages.

Subtasks

For each subtask, you will get $0$ points if your program fails to capture the Great Seedling (outputs an incorrect answer, outputs in the incorrect format, terminates unexpectedly, etc.) for any test case in the subtask. Otherwise (i.e. if you passed all test cases), you will get partial or full marks according to the maximum number of half-hours used to capture the Great Seedling across all testcases in the subtask.

1. ($50$ Points): The Great Seedling does not move between trees.
   Let $T$ be the number of half-hours it takes for Applejack and Apple Bloom to catch the Great Seedling. You will get:

   • $0$ points if $T > 32$.

   • $47 - 2(T-16)$ points if $16 < T \leq 32$.

   • $50$ points if $T \leq 16$.

2. ($50$ Points): The Great Seedling must move to an adjacent tree every half-hour.
   Let $T$ be the number of half-hours it takes for Applejack and Apple Bloom to catch the Great Seedling. You will get:

   • $0$ points if $T > 32$.

   • $47 - 2(T-16)$ points if $16 < T \leq 32$.

   • $50$ points if $T \leq 16$.

Sample interaction

In this sample interaction, we will illustrate the case where the Great Seedling does not move between trees.

In this sample interaction, we will illustrate the case where the Great Seedling moves to an adjacent tree every half-hour.