37번 - 나머지를 만들어요

호반우는 $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$가 가장 작은 걸 찾아보자.

호반우가 가진 $N, M$이 $3, 6$일 때 가능한 $A, B$는 $(3, 4), (3, 5), (3, 6), (3, 7) \cdots$이며 이중 $A + B$가 가장 작은 건 $3, 4$이다. 여러분은 다음과 같은 쿼리를 출력해 호반우에게 최대 $100$번까지 질문을 할 수 있습니다. \begin{itemize} \item ? $X$ : $X$의 배수와 $N$과의 차이 중에서 가장 작은 값을 $M$으로 나눈 나머지를 물어봅니다. $(1 \leq X \leq 10^{9})$ \end{itemize} 질문을 한 후에는 질문의 답변인 음이 아닌 정수가 하나 주어집니다. 정답을 알아낸 경우 다음과 같이 출력하고 프로그램을 종료해야 합니다. \begin{itemize} \item ! $a$ $b$ : 가능한 $A, B$ 중에서 $A + B$가 가장 작은 건 $a, b$입니다. $A + B$가 가장 작은 게 여러 가지라면 그중 아무거나 출력합니다. $(0 \leq a \leq 10^{9} ; 1 \leq b \leq 10^{9})$ \end{itemize} 만약 $100$번을 초과하여 질문하거나 출력한 답이 정답이 아니라면 틀렸습니다를 받습니다. ! a b는 $100$번의 질문에 포함되지 않습니다. 각 줄을 출력한 후에는 표준 출력 버퍼를 비워주어야 합니다. 언어별로 표준 출력 버퍼를 비우는 방법은 다음과 같습니다. \begin{itemize} \item C: fflush(stdout) \item C++: cout.flush() \item Java/Kotlin: System.out.flush() \item Python: sys.stdout.flush() \item 이외의 언어: 각 언어의 레퍼런스를 참고합니다. \end{itemize} $N$과 $M$의 값은 프로그램이 시작할 때 정해지며 인터랙션 도중에 변하지 않습니다.