#241 convex-hull-and-queries

Statement

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

좌표평면 위에 $N$ 개의 점이 있다. 각 점은 $1$ 번부터 $N$ 번까지의 번호가 붙어 있으며 $i$ 번째 점 $P_i$ 는 $(X_i, Y_i)$ $(-10\,000 \le X_i, Y_i \le 10\,000)$ 에 있다. 모든 점의 좌표는 정수이며 어떤 세 점도 한 직선 위에 있지 않다.

당신은 이 중 몇 개의 점을 골라 그 점들의 볼록 껍질에 포함되는 점을 인터랙터에게 최대

$\left\lceil \frac{N}{2} \right\rceil$ 번 물어볼 수 있다. 당신은 모든 점의 좌표를 알아내야 한다.

이 문제의 인터랙터는 적응적이지 않다. 즉, 인터랙터는 여러분의 질문에 따라 점의 좌표를 바꾸지 않는다.

Input

첫 번째 줄에 점의 개수 $N$ ( $10 \le N \le 100$ )이 주어진다.

Interactor

당신은 인터랙터에게 다음 쿼리를 최대 $\left\lceil \frac{N}{2} \right\rceil$ 번 요청할 수 있다.

? $M$ $M$ $A_1$ $A_{1}$ $A_2$ $A_{2}$ $...$ $...$ $A_M$ $A_{M}$ $(3 \le M \le N;$ $(3 \leq M \leq N;$ $1 \le A_i \le N;$ $1 \leq A_{i} \leq N;$ $i \neq j$ $i \neq = j$ 면 $A_i \neq A_j)$ $A_{i} \neq = A_{j})$ : $P_{A_1}$ $P_{A_{1}}$ , $P_{A_2}$ $P_{A_{2}}$ , $\cdots$ $\dots$ , $P_{A_M}$ $P_{A_{M}}$ 의 볼록 껍질이 무엇인지 질문한다.
- 쿼리의 결과로 볼록 껍질의 꼭짓점의 개수와 좌표가 공백으로 구분되어 주어진다. 볼록 껍질의 꼭짓점이 $m$ 개라면 $m$ $X_{B_1}$ $Y_{B_1}$ $X_{B_2}$ $Y_{B_2}$ $\cdots$ $X_{B_m}$ $Y_{B_m}$ 와 같이 $2m+1$ 개의 정수가 공백으로 구분되어 주어지며, $P_{B_i}$ 는 볼록 껍질의 꼭짓점이다. 볼록 껍질의 꼭짓점이 임의 순서로 주어짐에 유의해야 한다.

모든 점의 좌표를 알아냈다면 정답을 다음과 같이 출력하고 표준 출력 버퍼를 비우고 프로그램을 즉시 종료해야 한다. 즉시 종료하지 않는 경우 예상치 못한 결과를 얻을 수 있다.

! $x_1$ $y_1$ $x_2$ $y_2$ $...$ $x_N$ $y_N$

Samples

Input

4
3 2 0 0 -1 0 1

3 0 -1 2 0 0 1

Output

​

? 4 1 2 3 4

? 3 1 2 3

! 2 0 0 -1 0 1 1 0

위 예시는 입출력이 어떤 방식으로 이루어지는지 이해를 돕기 위해 의도적으로 개행 간격 등을 조절한 것으로, 실제 입출력과는 다르다. 또한 $N = 4$ 인 경우는 실제 테스트케이스에서 입력으로 주어지지 않는다.

프로그램은 처음 두 번의 질문과 문제의 조건에 의해 $4$ 번 점의 위치가 $(1, 0)$ 임을 알 수 있었지만 $1$ , $3$ 번 점의 순서는 알 수 없어 임의 순서로 배열하였다.

볼록 껍질은 주어진 점을 모두 포함하는 가장 작은 볼록 다각형이다. 볼록 껍질은 항상 유일하게 존재한다.

볼록 껍질과 쿼리

Statement

Input

Interactor

Samples