대화형 요격

시간 제한2초메모리 제한512 MB

요약

0부터 p까지의 시작 위치와 0부터 v까지의 속도가 정해지지 않은 점을, 매초 현재 위치가 구간 안에 있는지 묻는 질의 100회 이내로 찾아야 합니다.

문제

북동부 비상 로켓 관제 기관(NEERC)은 탄도 로켓 요격을 더 정밀하게 제어하기 위한 새 레이더 제어 시스템을 개발했다. NEERC는 이 시스템이 할 수 있는 일을 보여 주기 위해 수학적 모델을 만들었다.

로켓은 직선 위의 한 점으로 나타낸다. 처음에 점은 0 이상 $p$ 이하의 알 수 없는 정수 위치에 있다. 점의 알 수 없는 정수 속력 $q$ 는 0 이상 $v$ 이하이다.

매 초마다 다음이 일어난다. 먼저 제어 시스템이 check L R 형식의 질의를 레이더에 보낸다. 레이더는 점이 지금 L 이상 R 이하인 범위에 있는지 아닌지를 답한다. 그 다음 점의 좌표가 $q$ 만큼 증가한다.

제어 시스템은 어떤 초의 시작 시점에서 점의 정확한 위치를 알아내야 한다. 위치를 알아내면 질의 대신 그 위치에서 점을 요격하라는 명령을 내린다. 제어 시스템은 레이더에 최대 100번까지만 질의하고, 점의 위치를 찾아 요격해야 한다.

예시에서 점은 처음에 위치 1에 있고, 속력 $q = 1$ 로 움직인다.

예제 1

입력

2 2
Yes
No
Yes
Yes

예상 출력

check 1 3
check 3 5
check 2 4
check 4 5
answer 5