#P1088D. Ehab and another another xor problem

    ID: 4902 Type: RemoteJudge 1000ms 256MiB Tried: 0 Accepted: 0 Difficulty: 7 Uploaded By: Tags>bitmasksconstructive algorithmsimplementationinteractive*2000

Ehab and another another xor problem

Description

This is an interactive problem!

Ehab plays a game with Laggy. Ehab has 2 hidden integers (a,b)(a,b). Laggy can ask a pair of integers (c,d)(c,d) and Ehab will reply with:

  • 1 if ac>bda \oplus c>b \oplus d.
  • 0 if ac=bda \oplus c=b \oplus d.
  • -1 if ac<bda \oplus c<b \oplus d.

Operation aba \oplus b is the bitwise-xor operation of two numbers aa and bb.

Laggy should guess (a,b)(a,b) with at most 62 questions. You'll play this game. You're Laggy and the interactor is Ehab.

It's guaranteed that 0a,b<2300 \le a,b<2^{30}.

See the interaction section.

To print the answer, print "! a b" (without quotes). Don't forget to flush the output after printing the answer.

Interaction

To ask a question, print "? c d" (without quotes). Both cc and dd must be non-negative integers less than 2302^{30}. Don't forget to flush the output after printing any question.

After each question, you should read the answer as mentioned in the legend. If the interactor replies with -2, that means you asked more than 62 queries and your program should terminate.

To flush the output, you can use:-

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

Hacking:

To hack someone, print the 2 space-separated integers aa and bb (0a,b<230)(0 \le a,b<2^{30}).

Input

See the interaction section.

Output

To print the answer, print "! a b" (without quotes). Don't forget to flush the output after printing the answer.

Sample Input 1

1
-1
0

Sample Output 1

? 2 1
? 1 2
? 2 0
! 3 1

Note

In the sample:

The hidden numbers are a=3a=3 and b=1b=1.

In the first query: 32=13 \oplus 2 = 1 and 11=01 \oplus 1 = 0, so the answer is 1.

In the second query: 31=23 \oplus 1 = 2 and 12=31 \oplus 2 = 3, so the answer is -1.

In the third query: 32=13 \oplus 2 = 1 and 10=11 \oplus 0 = 1, so the answer is 0.

Then, we printed the answer.