대화형 보물 찾기

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

요약

n×m 격자에 숨겨진 보물 두 개를 DIG와 SCAN 질의 합계 7회 이내로 찾는 문제이며, SCAN은 좌표에서 두 보물까지 맨해튼 거리의 합을 돌려줍니다.

문제

이 문제는 대화형(interactive) 문제입니다.

격자판은 $n\times m$ 칸이다. 서로 다른 두 칸에 보물 상자 두 개가 묻혀 있다. 두 보물을 모두 찾아야 한다. 두 종류의 연산을 사용할 수 있다.

DIG $r$ $c$ : 칸 $(r, c)$ 에서 보물을 찾는다. 보물을 찾았는지는 인터랙터가 알려준다.
SCAN $r$ $c$ : 칸 $(r, c)$ 에서 스캔한다. 결과는 $(r, c)$ 에서 보물이 묻힌 두 칸까지의 맨해튼 거리의 합이다. $(r_1, c_1)$ 에서 $(r_2, c_2)$ 까지의 맨해튼 거리는 $|r_1 - r_2| + |c_1 - c_2|$ 이다.

최대 7번의 연산 안에 두 보물을 모두 찾아야 한다. 이 횟수에는 DIG와 SCAN이 모두 포함된다. 테스트를 통과하려면 보물이 묻힌 두 칸 각각에 대해 DIG를 최소 한 번 호출해야 한다.

예제 1

입력

예상 출력



SCAN 1 2

DIG 1 2

SCAN 2 2

DIG 1 1

DIG 1 3