Problem AK
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 will 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.

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 $16$ 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\le N\le {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:

  • $\mathtt{\text{Q}}{l}_1{r}_1{l}_2{r}_2$ ($1\le l_1\le r_1\le N$; $1\le l_2\le r_2\le 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 $16$ times.

  • $\mathtt{\text{A}}t$ ($1\le t\le 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\le w_1,w_2\le 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.

Sample interaction