Mettaton Attacks

Limits 1s, 512 MB · Interactive

This is an interactive problem.

Mettaton, the star of underworld TV show attacks you again with his pop quiz! Oh, you never played before? No problem! It's simple! There's only one rule. Answer correctly... or you lose 50% of your points in every wrong submission.

Mettaton's quiz show consists of a set of multiple choice questions. There are a total of $T$ questions, each with a total of $N < 2^{60}$ options, numbered from 1 to $N$ and only one of them is correct, labeled $H$. Your task is to find out $H$ ($H < 2^{60}$).

Ofcourse you aren't alone in this, the underground researcher Alphys is with you. Last time he got caught supplying participants with answers using hand signs, so he can't do that again. But worry not, he has devised a nice plan and installed an application in your phone.

Each time you use your the phone, you give it two integers $L$ and $R$. Now Alphys tells you, the number of integers $x$ such that $L \leq x \leq R$ where $x \oplus H$ can be written as a power of 2. More formally, $x \oplus H = 2^k$ and $k$ is a non-negative integer ($\oplus$ is the bitwise xor operation).

Since it is a live show, you don't have too much time to use the phone. You calculated that, you have just enough time to use the phone $Q$ times. But you don't have to use your phone to tell the answer to Mettaton.

Input

Read the value of $T$( $T \leq 500$), which is the number of questions. Then you can start interacting.

If you want to use the phone, print ? L R . Then you can read an integer which is what Alphys told you. You must ensure that $0\leq L \leq R < 2^{63}$ and you haven't exceeded your asking limit $Q$ ($Q \leq 69$). In which case judge will give you -1 as the answer, and you must terminate your program immediately.

Once you have figured out the answer to a question, tell Mettaton like this ! h where h is the answer you found. Then the judge outputs "OK" if your answer was correct or, "WA" otherwise. If you read "WA" you must terminate your program. If you got "OK" proceed to the interaction of your next question immediately (if there is any).

Terminate where you were told, otherwise you might get TLE or other random verdicts instead of WA.

Also remember to print newlines and flush the output after every ? L R or ! h operation. You can use:

• fflush(stdout) or cout.flush() in C++
• System.out.flush() in Java
• flush(output) in Pascal
• stdout.flush() in Python
• See documentation of other languages.

Output

You only interact with the judge. There is no other output you need to print.

Interaction Example:

Here is an example of how your program will interact with the judge. > indicates you print something, < indicates you take input from judge.

< 2 Mettaton has 2 questions.
> ? 1 5You use the phone.
< 2 Alphys replies.
> ? 3 3 You use the phone again.
< 0 Alphys replies.
> ! 3 You miraculously found the answer?
< OK Mettaton agrees!!!
> ! 69 You answer without even asking.
< OK .....