32304번 - 나머지를 만들어요 인터랙티브

이 문제는 인터랙티브 문제입니다.

호반우는 $10^{9}$ 이하의 음이 아닌 정수 $N$과 양의 정수 $M$을 가지고 있는데 $N$과 $M$이 무엇인지 궁금해하는 상호에게 다음과 같은 제안을 했다.

"$10^{9}$이하의 양의 정수 $X$를 고르면 $X$의 배수와 $N$과의 차이 중에서 가장 작은 값을 $M$으로 나눈 나머지를 알려줄게. 단, 질문은 최대 $100$번까지 할 수 있어."

호반우는 상호가 예측한 $N, M$이 자신이 가진 $N, M$과 달라도 $10^{9}$ 이하의 모든 양의 정수 $X$에 대한 질문에서 대답이 일치한다면 정답으로 인정하려 한다.

상호가 $N, M$으로 예측한 수가 $A, B$이고 호반우가 이를 정답으로 인정했을 때 가능한 $A, B$ 중에서 $A + B$가 가장 작은 걸 찾아보자.

호반우에게 다음과 같은 쿼리를 출력해 최대 $100$번까지 질문을 할 수 있다.

• ? X: $X$의 배수와 $N$과의 차이 중에서 가장 작은 값을 $M$으로 나눈 나머지를 물어본다. $(1 \leq X \leq 10^{9})$

질문을 한 후에는 질문의 답변인 음이 아닌 정수가 하나 주어진다.

정답을 알아낸 경우 다음과 같이 출력하고 프로그램을 종료해야 한다.

• ! a b: 가능한 $A, B$ 중에서 $A + B$가 가장 작은 것은 $a, b$이다. $A + B$가 가장 작은 것이 여러 가지라면 그중 아무거나 출력한다. $(0 \leq a \leq 10^{9} ; 1 \leq b \leq 10^{9})$

만약 $100$번을 초과하여 질문하거나 출력한 답이 정답이 아니라면 틀렸습니다를 받는다. ! a b는 $100$번의 질문에 포함되지 않는다.

각 줄을 출력한 후에는 표준 출력 버퍼를 비워주어야 한다. 언어별로 표준 출력 버퍼를 비우는 방법은 다음과 같다.

• C: fflush(stdout)
• C++: cout.flush()
• Java: System.out.flush()
• Python: sys.stdout.flush()
• 이외의 언어 : 각 언어의 레퍼런스를 참고한다.

$N$과 $M$의 값은 프로그램이 시작할 때 정해지며 인터랙션 도중에 변하지 않는다.

출력 형식이나 제한을 지키지 않은 경우 예상치 못한 채점 결과를 받을 수 있다.