랜덤 게임?

문제

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

처음에 인터랙터는 $1$ 부터 $N$ 까지 정수 중에서 균등한 확률로 수를 하나를 뽑는다. 질문을 통해 인터랙터가 현재 가지고 있는 수를 맞추면 이 문제를 맞힐 수 있다.

당신은 다음과 같은 질문을 최대 $20\\,000$ 번 할 수 있다.

현재 가지고 있는 수가 $x$ 인가? $(1\le x\le N)$

만약 질문의 답이 '아니오.'라면 인터랙터는 현재 가지고 있는 수를 버리고 새로 수를 뽑는다.

입력

양의 정수 $N$ 이 주어진다. $(1 \le N \le 1\\,000)$

출력

다음을 표준 출력 스트림(stdout)으로 한 줄에 출력하여, 인터랙터가 가지고 있는 수가 무엇인지 질문할 수 있다.

? x : 현재 인터랙터가 가지고 있는 수가 $x$ 인지 확인한다. $(1\le x\le N)$

질문을 한 뒤, 당신은 인터랙터에게서 문자 하나를 입력받아서 질문의 답을 알 수 있다.

Y : 현재 인터랙터가 가지고 있는 수는 $x$ 와 같다.
N : 현재 인터랙터가 가지고 있는 수는 $x$ 와 다르다. 이후 인터랙터는 현재 가지고 있는 수를 버리고 새로 수를 뽑는다. 수를 뽑을 때는 질문의 답을 참고하지 않고 $1$ 부터 $N$ 까지 정수 중에서 균등한 확률로 수를 하나를 뽑는다.

질문을 한 후에는 반드시 표준 출력 버퍼를 flush 해야 하고, 표준 입력 스트림(stdin)을 통해 질문에 대한 답을 입력받아야 한다. 그렇지 않으면, 시간 초과 또는 런타임 에러를 받는다. 범위를 벗어난 $x$ 값을 질문하거나 잘못된 형식으로 질문하면 틀렸습니다를 받는다. 또한 $20\\,000$ 회 넘게 질문을 하면 틀렸습니다를 받는다.

만약 인터랙터가 현재 가지고 있는 수를 알아낸 경우, 표준 출력 스트림으로 다음 한 줄을 출력한다.

! y : 현재 인터랙터가 가지고 있는 수는 $y$ 이다.

답을 출력한 이후에는 표준 출력 버퍼를 비우고 프로그램을 바로 종료하여야 한다. 그렇지 않으면 예상하지 못한 채점 결과를 받을 수 있다.

각 언어별로 표준 출력 버퍼를 flush하는 방법은 다음과 같다.

C: fflush(stdout)
C++: std::cout << std::flush
Java: System.out.flush()
Python: sys.stdout.flush()