Problem M
Dragon Dropped

Rarity and Spike are best friends who often spend a lot of time together. Recently, however, Spike’s griffon pen pal Gabby from Griffonstone has come to town to work mail delivery, and he has decided to accompany her in her daily shifts, leaving little time for Rarity.

Figure 1: Illustration by Kyle Coate.

Without Spike’s company, Rarity has begun to feel lonely. She decides that it would be a good idea to meet Gabby and Spike right where they end their shift so that she can invite both of them to hang out.

The only issue is that Rarity does not know where their shift ends. She knows that Gabby has an extremely regular shift:

1. The shift always begins at the Ponyville post office.

2. The shift never returns to the Ponyville post office.

3. Excluding the Ponyville post office, the shift involves at most $6\, 000$ distinct locations.
   That is, if one runs the entire shift, one would have encountered at most $6\, 000$ distinct locations.

4. The shift ends after visiting exactly $N$, not necessarily distinct, locations. Note that the beginning at the Ponyville post office does not count as a visit.

5. The next location on the shift, if it exists, is always distinct from the current location.

6. The next location on the shift, if it exists, depends only on the current location.
   That is, if the $x^\text {th}$ and $y^\text {th}$ location on the shift are the same, then the $(x+1)^\text {th}$ and $(y+1)^\text {th}$ location on the shift, if they exist, are also the same.

This information is not enough to know where their shift ends, so today, Rarity decided to meet Gabby and Spike at the Ponyville post office at dawn, a few hours before their shift starts, to request them to show her around. Genteel to a fault, she does not want to be too forward and just ask them directly where their shift ends—that would be rude—instead, she needs to at least pretend to be interested in their work. In one request, Rarity can either:

1. Ask Gabby to visit the next location on the shift. If there are no more locations on the shift, Gabby will inform Rarity of that and stay where she is;

2. Ask Spike to visit the next location on the shift. If there are no more locations on the shift, Spike will inform Rarity of that and stay where he is;

3. Ask Gabby to return to the Ponyville post office, restarting the shift;

4. Ask Spike to return to the Ponyville post office, restarting the shift.

Recall that Spike typically accompanies Gabby and therefore they are both knowledgeable of and follow the same shift.

After each request, Rarity will take note of whether Gabby and Spike are at the same location, but otherwise unfortunately is not familiar enough with the locations to know exactly where they are. Thus, either Gabby or Spike needs to be at the ending location once she ascertains which one it is; she will then ask for a few details about this place before letting her or him return to call the other and get ready for work.

She only has time to make $30\, 000$ requests before Gabby and Spike have to begin their shift. Help her determine where their shift ends!

Interaction

First, your program should read a single integer $N$ ($1 \leq N \leq 10^9$), the number of locations after which the shift ends on a single line from standard input.

Then, we repeat the following process:

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

  • NEXT GABBY, meaning that Rarity should ask Gabby to visit the next location on the shift.

  • NEXT SPIKE, meaning that Rarity should ask Spike to visit the next location on the shift.

  • RETURN GABBY, meaning that Rarity should ask Gabby to return to the Ponyville post office, restarting the shift.

  • RETURN SPIKE, meaning that Rarity should ask Spike to return to the Ponyville post office, restarting the shift.
    The above four requests can be done a total of at most $30\, 000$ times.

  • ASK GABBY, meaning that you are sure that the location Gabby is at now is precisely where they will end their shift, and Rarity should ask her for a few details about this place before letting her return to call Spike and get ready for work.

  • ASK SPIKE, meaning that you are sure that the location Spike is at now is precisely where they will end their shift, and Rarity should ask him for a few details about this place before letting him return to call Gabby and get ready for work.

• If your program makes a request, your program should read two integers $s$ and $e$ ($0 \leq s, e \leq 1$) from standard input. If $s = 0$, it means that you asked either Gabby or Spike to visit the next location on the shift but there were no more locations on the shift; in all other cases $s = 1$. If $e = 0$, it means that after your request, Gabby and Spike are at different locations; if $e = 1$, it means that after your request, Gabby and Spike are at the same location.

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

After making a request or declaring the ending location, 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.

The input will be such that there is always a way to determine the ending location within $30\, 000$ requests.

Sample interaction