Problem D
Divide Doughnut

This is an interactive problem.

Khue and Hanh are obsessed with doughnuts although they are very much overweight. Over the last week, they worked very hard setting up the problems for ICPC Hanoi. To prepare for a long night of coding, they bought a super-large ring-shaped doughnut.

The perimeter of this doughnut is $1$ meter. They like things to be super precise so they divided the doughnut into ${10}^{9}$ parts, The outermost length of each of them is $1$ nanometer. They are numbered from $0$ to ${10}^{9}-1$.

This doughnut was topped with exactly $N$ ($N$ is even) sprinkles. No two sprinkles are in the same part. Khue and Hanh wants to divide the doughnut so that:

• Khue has $5 \cdot {10}^{8}$ consecutive parts. These parts have exactly $N/2$ sprinkles.

• Hanh has $5 \cdot {10}^{8}$ consecutive parts. These parts have exactly $N/2$ sprinkles.

In order to divide, they use an image processing program to count the number of sprinkles in consecutive parts.

You task is to divide the doughnut for Khue and Hanh without using the image processing program too many times. If there are multiple ways to divide the doughnut that satisfy the above conditions, you can answer with any of them.

Interaction

First your program reads the total number of sprinkles $N$ $(1 \leq N \leq 100\, 000)$ from the standard input. It is guaranteed that $N$ is even. Then the following process repeats:

• Your program write to the standard output one of the following:

  • QUERY u v $(0 \leq u,v < {10}^{9})$ — count the number of sprinkles from part $u$ to part $v$. Please note that: $u>v$ means count the number of sprinkles from part $u$ to ${10}^{9}-1$ and $0$ to $v$.

  • YES x $(0 \leq x < {10}^{9})$ — You answer Khue should get parts from $x$ to $(x + 5 \cdot {10}^{8} - 1) \bmod {10}^{9}$.

  • NO — You answer there is no division that satisfies Khue and Hanh.

• If your program asks a query, an integer $S$ will be available in the standard input. Your program should then read it.

• Otherwise, your answer will be checked. Your program should terminate immediately after this.

You are allowed to interact at most $30 + \left\lfloor { \log _{2}{\sqrt {N}} } \right\rfloor $ times, including giving an answer.

Communication example

Note

When you write the solution for the interactive problem it is important to keep in mind that if you output some data it is possible that this data is first placed to some internal buffer and may be not directly transferred to the interactor. In order to avoid such situation you have to use special ‘flush’ operation each time you output some data. There are these ‘flush’ operations in standard libraries of almost all languages. For example, in C++ you may use fflush(stdout) or cout $<<$ flush (it depends on what do you use for output data — scanf/printf or cout). In Java you can use method ‘flush’ for output stream, for example, System.out.flush(). In Python you can use stdout.flush().