$n$개의 정점을 가진 단순 무향 그래프가 있다. 이 그래프는 다음과 같은 추가적인 성질을 만족한다.

• 모든 유도 부분 그래프(induced subgraph)는 차수가 $k$ 이하인 정점을 적어도 하나 포함한다.

당신은 이 숨겨진 그래프를 찾아야 한다. 임의의 부분 집합에 대해 독립 집합(independent set)인지 확인할 수 있다. 만약 독립 집합이 아니라면, 해당 부분 집합 내의 두 끝점을 포함하는 간선을 알려줄 것이다.

상호작용 중에 그래프는 변하지 않으므로, 그래프는 고정되어 있다고 가정해도 좋다. 하지만 유도 부분 그래프 내의 어떤 간선을 보여줄지는 우리가 선택할 수 있다. 즉, 모든 테스트 케이스에서 그래프는 고정되어 있지만, 인터랙터는 적응형(adaptive)이다.

당신은 최대 $2nk + n$번의 질의 내에 그래프를 추측해야 한다.

인터랙션

상호작용은 숨겨진 그래프의 정점 수 $n$ ($2 \le n \le 2000$)을 포함하는 한 줄로 시작한다.

정수 $k$는 주어지지 않지만, $1 \le k < n$ 및 $nk \le 2000$이라는 제약을 만족한다.

그 후, 질의를 수행할 수 있다. 질의를 하려면 "? $m$" ($1 \le m \le n$)과 $m$개의 서로 다른 정수 $v_1, v_2, \dots, v_m$ ($1 \le v_i \le n$)을 한 줄에 출력한다. 연속된 정수는 공백으로 구분한다. 그 후 출력을 flush 해야 한다.

각 질의 후, 두 정수 $i, j$를 읽는다. 유도 부분 그래프 $v_1, v_2, \dots, v_m$ 내에 간선이 없으면 $i = j = -1$이다. 그렇지 않으면 $i \neq j, i \in \{v_1, \dots, v_m\}, j \in \{v_1, \dots, v_m\}$이며, 그래프 내에 $i$와 $j$를 잇는 간선이 존재한다.

그래프를 찾으면, 첫 줄에 "! $m$"을 출력한다. 그 다음 $m$줄에는 그래프의 간선 정보를 출력하며, 각 줄은 간선으로 연결된 두 정점의 인덱스 $u, v$ ($1 \le u, v \le n$)를 포함해야 한다.

$2nk + n$번보다 많은 질의를 수행하면 Wrong Answer 또는 Time Limit Exceeded를 받게 된다. 아무것도 출력하지 않거나 출력을 flush 하는 것을 잊으면 Idleness Limit Exceeded를 받게 된다.

질의와 줄 바꿈을 출력한 직후에 다음을 수행하여 flush 해야 한다:

• C++의 경우 fflush(stdout) 또는 cout.flush();
• Java의 경우 System.out.flush();
• Pascal의 경우 flush(output);
• Python의 경우 stdout.flush();
• 다른 언어는 해당 언어의 문서를 참조하십시오.

예제

입력 1

3
1 2
2 3
1 3

출력 1

? 2 1 2
? 2 2 3
? 2 1 3
! 3
1 2
2 3
1 3