31930번 - AK47 인터랙티브

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

밤마다 총성이 울리는 동네에 일렬로 배치된 $N$개의 구역이 있다. 이 중 서로 다른 두 구역에 보물이 숨겨져 있으며, 나머지 구역에는 폭탄이 설치되어 있다. 엄마를 요양원 보내기 위한 비용이 필요한 이삭이는 두 보물을 모두 훔치기로 마음먹었다. 폭탄이 설치된 구역에 접근하면 폭탄이 폭발하므로, 이삭이는 보물이 위치한 두 구역을 정확히 파악하려고 한다.

보물은 악소리에 반응하며 외할머니는 일렬로 연속한 구간에 소리가 닿도록 악소리를 낼 수 있다. 이때, 소리가 닿은 구간 내 구역에 보물이 정확히 하나 존재할 때만 보물의 반응을 느낄 수 있다. 보물이 존재하지 않는다면 보물이 반응하지 않으므로 반응을 느낄 수 없고, 두 보물이 모두 존재한다면 두 보물의 반응이 중첩되어 반응을 느낄 수 없다.

외할머니는 악소리를 $47$번 이내로 낼 수 있다. 외할머니를 도와 이삭이가 두 보물을 모두 훔칠 수 있도록 하자.

첫째 줄에 테스트 케이스의 개수 $T$가 주어지며, 그다음 줄부터 각 테스트 케이스의 입력이 주어진다. $(1\leq T \leq 47)$

각 테스트 케이스에서 인터랙션의 응답으로서 주어지는 입력이 아닌 초기 입력은 한 줄로 이루어져 있으며, 구역의 수 $N$이 주어진다. $(2\leq N \leq 92)$

$N$을 입력받은 후, 인터랙션이 시작된다.

다음을 표준 출력 스트림(stdout)으로 한 줄에 출력하여, 악소리를 낼 수 있다. 한 줄에 출력한다는 것은, 개행문자('\n')까지 출력해야 한다는 것임에 유의하자.

• AK l r: $l$번째 구역부터 $r$번째 구역까지 일렬로 연속한 구간 내 구역에 보물이 정확히 하나 존재하는지 확인한다. $(1\leq l\leq r\leq N)$

이에 대한 답으로 문자 하나를 입력받아 보물의 반응을 느꼈는지 확인할 수 있다.

• O: 보물이 정확히 하나 존재한다.
• X: 보물이 없거나 두 보물이 모두 존재한다.

악소리를 낸 후에는 반드시 표준 출력 버퍼를 flush 해야 하고, 표준 입력 스트림(stdin)을 통해 보물의 반응을 느꼈는지 여부를 입력받아야 한다. 그렇지 않으면, 시간 초과 또는 런타임 에러를 받는다. 범위를 벗어나거나 잘못된 형식으로 출력하면 틀렸습니다를 받는다. 또한 각 테스트 케이스에서 $47$번 넘게 악소리를 내면 틀렸습니다를 받는다.

보물의 위치는 악소리를 냄에 따라 변하지 않는다. 즉, 비적응적(non-adaptive)이다.

보물이 위치한 두 구역을 알아낸 경우, 표준 출력 스트림으로 다음 한 줄을 출력한다. 이것은 악소리를 내는 횟수에 포함되지 않는다. 마찬가지로, 개행문자('\n')까지 출력해야 함에 유의하자.

• ! a b: 보물이 위치한 구역은 $a$번째 구역과 $b$번째 구역이다. $(1\leq a,b\leq N)$

답을 출력한 이후에는 표준 출력 버퍼를 flush 하고 바로 다음 테스트 케이스의 입력을 받아야 하며, 마지막 테스트 케이스인 경우에는 프로그램을 바로 종료하여야 한다. 그렇지 않으면 예상하지 못한 채점 결과를 받을 수 있다.

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

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