27943번 - 가지 사진 찾기 인터랙티브

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

가지 나라의 연구소에는 매우 큰 데이터베이스가 있다. 이 데이터베이스에는 매년 전국에서 인터넷에 업로드된 사진이 모두 들어간다. 모인 사진에는 온갖 종류의 사물이 담겨 있지만, 각 사진에 찍힌 사물은 유일하다. 사진이 계속 올라오는 한 해 동안은 사진이 정렬되어 있지 않지만, 그해가 끝나면 모았던 사진들을 예쁘게 배열해서 같은 종류의 사물을 찍은 사진들에 연속된 번호를 부여한다. 예를 들어, 데이터베이스가 거의 사용되지 않았던 2020년도에는 애벌레 사진이 1번부터 2번까지를, 텐트 사진이 3번부터 5번까지를, 축구공 사진이 6번을, 그리고 가지 사진이 7번부터 22번까지의 번호를 받았고, 이 22개 사진이 현재 업로드된 2020년도 사진의 전부라고 한다.

데이터과학자 와파스는 작년 2022년에 올라온 가지 사진을 다운로드받기 위해 데이터베이스를 이용하려고 한다. 사전에 접한 정보에 따르면, 2022년에도 어김없이 업로드된 사진 중에 가지 사진의 비율은 절반이 넘는다고 한다. 사진이 엄청나게 많으니 제발 필요한 데이터만 효율적으로 다운로드하라고 잔소리를 듣는 와파스를 위해, 데이터베이스에서 가지 사진의 번호가 몇 번부터 몇 번까지인지 대신 구해주자.

첫 줄에 2022년도 사진의 총 개수 $n$ $(3\le n \le 10^{18})$이 주어진다.

당신은 총 $120$번까지, 특정 번호의 사진이 어느 사물을 담고 있는지 질문할 수 있다. 번호 $x$는 $1 \le x \le n$을 만족해야 하며, 질문은 ? x와 줄바꿈을 출력하는 것으로 가능하다. 질문의 답변은 사진에 담긴 물건의 이름을 의미하는 문자열 한 줄로 주어진다. 이름은 영문 알파벳 소문자 a-z와 숫자 0-9로만 구성되어 있으며, 이름의 길이는 $1$ 이상 $20$ 이하이다. 가지를 가리키는 이름은 미리 알 수 없으며, 질문을 통해 알아내야 한다.

충분한 질문 끝에 가지 사진 번호의 범위를 알아냈다면, ! a b의 형식으로 답을 출력하고, 줄 바꿈을 출력한 후 종료한다. $a$는 가지 사진의 번호 중 최솟값, $b$는 최댓값이다.

모든 출력 뒤에 출력 버퍼를 비우지 않거나, 올바르지 않은 답을 출력하거나, 출력 형식을 어길 경우 예상하지 못한 채점 결과를 받을 수 있다.

예제는 입출력이 어떤 방식으로 이루어지는지 알기 쉽도록 의도적으로 줄 간격을 조정한 것으로, 실제 입출력과는 다르다.

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

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