28258번 - 초콜릿 보물 찾기 인터랙티브

한별이와 함께 어느 해변에 놀러 가기로 한 코코는 해변에 미리 와서 보물찾기 게임을 준비했다. 먼저 모래사장에 $10\times 10$ 크기의 격자를 그린 후, $100$개의 칸 중에서 가로 또는 세로로 이웃한 두 칸을 골라 $2\times 1$ 크기의 보물상자를 묻어 놓았다.

보물찾기 게임 준비를 마친 코코는 한별이에게 이런 제안을 했다. “최대 $50$칸만 파 보고 보물상자의 위치를 정확히 알아내면 보물상자에 든 초콜릿을 모두 줄게. 보물상자가 있는 두 칸을 모두 파낼 필요는 없고, 두 칸의 좌표만 맞으면 돼.” 과연 한별이는 보물상자의 초콜릿을 얻을 수 있을까?

다음을 한 줄에 출력하여 인터랙터에게 쿼리를 할 수 있다. 쿼리는 최대 $50$번까지 할 수 있다.

• ? r c : r행 c열을 파 본다. 행 번호와 열 번호는 $0$에서 시작하며, 따라서 올바른 값의 범위는 $0\le r,c\le 9$이다.

각 쿼리의 결과는 한 줄을 입력받아 알 수 있다. 가능한 결과는 다음과 같다.

• 1 : r행 c열에 보물상자의 일부가 있다.
• 0 : r행 c열에 보물상자의 일부가 없다.

쿼리를 출력한 후에는 반드시 표준 출력 버퍼를 flush해야 한다.

보물상자의 위치를 알아냈으면 다음과 같이 출력하고 flush한 후 프로그램을 종료해야 한다.

• ! r1 c1 r2 c2 : 보물상자는 r1행 c1열과 r2행 c2열에 걸쳐 있다. 좌표의 순서는 관계 없다. 보물상자의 위치가 맞으면 맞았습니다, 아니면 틀렸습니다를 받는다.

출력 형식을 지키지 않거나 쿼리를 $50$번보다 많이 한 경우에는 예상치 못한 채점 결과를 받을 수 있음에 유의한다.