젓가락으로 메추리알 집기

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

세로로 $N$개, 가로로 $M$개의 정사각형 칸들로 이루어진 반찬통이 있다. 쿠가 메추리알을 거의 다 먹어 치워 버렸기에, 반찬통 안에는 메추리알이 단 한 칸에만 놓여 있다.

당신은 눈을 가린 채로, 반찬통 안의 어딘가에 남아 있는 메추리알 하나를 젓가락으로 집어먹어 보려 한다!

$N = 2,\ M = 3$일 때, 반찬통 안에 메추리알이 놓여 있는 모습이다.

당신은 $\left\lfloor \dfrac{NM}{2} \right\rfloor$번의 젓가락질 이내로 메추리알을 잡아야 한다. 젓가락질은 다음 과정으로 이루어진다.

• 반찬통 안의 칸 하나를 골라 그 칸을 향해 젓가락질한다.

• 젓가락질한 칸에 메추리알이 있다면, 메추리알을 집는다.

• 젓가락질한 칸에 메추리알이 없다면, 메추리알은 다음 규칙에 따라 이동한다.

  • 젓가락질한 칸이 메추리알이 있는 칸과 인접하다면, 메추리알은 인접한 무작위 칸 중 하나로 이동한다. 단, 방금 젓가락질한 칸이나 반찬통 밖으로는 이동하지 않는다.
  • 젓가락질한 칸이 메추리알이 있는 칸과 인접하지 않는다면, 메추리알은 이동하지 않는다.

파란색 칸에 젓가락질하면 메추리알은 두 빨간색 칸 중 하나로 이동한다.

어떤 두 칸이 한 변을 공유하면 두 칸은 인접한다고 한다. 꼭짓점만을 공유하는 두 칸은 서로 인접하지 않는다.

정해진 젓가락질 횟수 안에 메추리알을 잡아보자!

첫째 줄에 반찬통의 크기를 나타내는 정수 $N$, $M$이 공백으로 구분되어 주어진다. $\left(2 \le N, \ M \le 100\right)$

당신은 표준 입출력으로 채점 시스템과 상호작용해야 한다. 다음과 같이 문자열을 한 줄에 출력하여 젓가락질할 수 있다.

• ? r c: 반찬통의 위에서 $r$번째, 왼쪽에서 $c$번째에 위치한 칸에 젓가락질한다. $(1 \le r \le N;$ $1 \le c \le M)$

당신은 최대 $\left\lfloor \dfrac{NM}{2} \right\rfloor$번 젓가락질할 수 있으며, 반찬통을 벗어나거나 횟수를 초과하는 경우 틀렸습니다를 받는다.

문자열을 출력한 이후, 당신은 젓가락질의 결과를 나타내는 정수 하나를 입력받아야 한다.

• 메추리알을 집었다면 1을 입력받는다.
• 메추리알을 집지 못했다면 0을 입력받고, 메추리알은 문제의 규칙에 따라 이동한다.

젓가락질의 결과로 1을 입력받았다면 프로그램을 즉시 종료해야 한다. 그렇지 않으면 예상하지 못한 채점 결과를 받을 수 있다.

각 행동을 출력한 이후, 프로그램은 매번 표준 출력을 flush해야 한다. 그렇지 않으면 시간 초과를 받을 수 있다. 대표적인 언어에서 표준 출력을 flush하는 방법은 다음과 같다.

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

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

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

예제에서 사용한 전략은 이해를 돕기 위한 것이며, 문제의 정답이 아닙니다.