젓가락으로 메추리알 집기

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

$N \times M$ 크기의 격자로 이루어진 반찬통이 있다. 반찬통 속 단 한 칸에 메추리알이 놓여 있다.

당신은 한계를 시험하기 위해 눈을 가린 채로 젓가락을 사용하여 반찬통 안의 메추리알을 집기로 했다. 따라서 당신은 메추리알의 위치를 모른다.

당신은 젓가락질을 $\lfloor \frac{NM}{2} \rfloor$번 이하로 하여 메추리알을 잡아야 한다.

• $r$번째 행, $c$번째 열에 위치한 칸 $(r,c) \ (1 \le r \le N, \ 1 \le c \le M)$에 젓가락질을 한다. 해당 칸에 메추리알이 있다면 을 반환한다. 그렇지 않다면 을 반환한다.

이 행동을 통해 메추리알을 잡았다면 프로그램을 즉시 종료해야 한다.

그렇지 않다면 메추리알은 다음과 같이 이동한다:

• 메추리알과 젓가락이 인접해있다면, 메추리알은 젓가락이 있는 칸을 제외한 상하좌우로 인접한 칸 중 하나의 무작위 칸으로 이동한다. 메추리알은 반찬통 밖으로 이동하지 않는다.
• 그렇지 않다면 메추리알은 이동하지 않는다.

어떤 두 칸이 인접하다는 것은 두 칸이 어떤 한 모서리를 공유함을 의미한다. 꼭짓점만을 공유하는 두 칸은 인접한 칸이 아니다.

주어진 질문 횟수 안에 메추리알을 잡아 보자.

인터랙터는 적응적이다. 메추리알의 시작 위치와 이동할 방향은 미리 정해져 있지 않다.

첫째 줄에 격자의 크기를 나타내는 정수 $N, \ M$이 주어진다. $(2 \le N, \ M \le 100)$

예제는 입출력이 어떤 방식으로 이루어지는지 이해를 돕기 위해, 의도적으로 줄 간격을 조절하였습니다. 실제 입출력과 다름에 유의해 주세요.

예제에서 사용한 전략은 항상 정해진 제한 안에 메추리알을 찾을 수 있음이 보장되지 않는 방법임에 유의하세요.

당신은 아래의 질문를 최대 $\lfloor \frac{NM}{2} \rfloor$번 이하로 출력해야 한다.

• $?\ r \ c$: 칸 에 젓가락질을 한다.