보물찾기

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

$100 \times 100$ 격자 위에 보물상자 $10$개가 숨겨져 있다.

격자의 행 번호와 열 번호는 모두 $1$ 이상 $100$ 이하의 정수이다. 격자의 한 칸은 두 정수 $(x,y)$로 나타내며, 이는 $x$행 $y$열의 칸을 의미한다.

당신은 인터랙터와 상호작용하며 보물상자의 위치를 모두 찾아야 한다. 모든 보물 상자의 위치는 서로 다르다.

사용할 수 있는 쿼리는 다음 두 종류이다.

• ? x y: 현재 남아 있는 보물상자 중 $(x,y)$와 맨해튼 거리가 가장 가까운 보물상자까지의 거리를 반환받는다.
• ! x y: 현재 $(x,y)$에 보물상자가 있음을 보고한다. 보고가 맞으면 해당 보물상자는 사라진다.

두 칸 $(x_1,y_1)$과 $(x_2,y_2)$ 사이의 맨해튼 거리는 $|x_1-x_2|+|y_1-y_2|$이다.

보물상자 $10$개의 위치를 모두 정확히 찾아내는 프로그램을 작성하여라.

프로그램 시작 시 참가자 프로그램에 주어지는 입력은 없다. 따라서 바로 쿼리를 시작하면 된다.

참가자 프로그램은 표준 출력으로 쿼리를 출력하고, 표준 입력으로 인터랙터의 응답을 읽어야 한다.

? 쿼리는 다음 형식으로 출력한다.

? x y

이때 $1 \le x,y \le 100$이어야 한다. 이 쿼리에 대해 인터랙터는 현재 남아 있는 보물상자 중 $(x,y)$와의 맨해튼 거리의 최솟값을 정수 하나로 반환한다.

! 쿼리는 다음 형식으로 출력한다.

! x y

이때 $1 \le x,y \le 100$이어야 한다. 현재 $(x,y)$에 보물상자가 있으면 인터랙터는 1을 반환하고, 해당 보물상자는 사라진다. 현재 $(x,y)$에 보물상자가 없으면 오답 처리된다.

! 쿼리를 정확히 $10$번 성공하면 참가자 프로그램은 즉시 종료해야 한다.

각 쿼리를 출력한 뒤에는 반드시 출력 버퍼를 비워야 한다.

인터랙터는 적응적이다.

• 격자의 크기는 $100 \times 100$이다.
• 보물상자의 개수는 $10$개이다.
• 모든 보물상자는 서로 다른 칸에 있다.
• 모든 쿼리에서 $1 \le x,y \le 100$이어야 한다.
• ? 쿼리는 최대 $10\,000$번 사용할 수 있다.
• ! 쿼리는 점수 계산에 포함되지 않는다.

? 쿼리를 사용한 횟수를 $Q$라고 하자. 점수 $S$는 다음과 같이 정해진다.

단, 보물상자 $10$개의 위치를 모두 정확히 보고하지 못하거나 잘못된 쿼리를 사용하면 점수는 $0$점이다.

쿼리 수에 따른 점수 분포는 다음과 같다.