시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 44 9 5 41.667%

문제

고대 문명이 발견되자, 고고학자들은 궁금증이 생겼습니다. 대체 그 먼 옛날에 어떻게 문명이 생겼던 것일까요? 그리고 지금은 왜 그 흔적을 찾아보기 힘들게 된 것일까요? 당신은 고대 문명의 비밀을 알아내고자 합니다.

언어학자들이 고대의 기록을 분석한 결과, 폴리매스 문명을 유지해주는 동력원인 다섯 개의 돌이 있는 것으로 추측되고 있습니다. 이들은 현재 지구상에 존재하지 않는 물질로 이루어져 있던 것으로 보이며, 문명의 발원지에 신비한 힘을 일으켜 문명이 발전하기에 적합한 환경을 만들어 주었을 것입니다.

최근에 돌의 유해로 추정되는 $N+5$개의 조각이 발견되었습니다. 당신은 각 조각이 어떤 돌의 유해인지 알아내려고 합니다. 복잡한 연구를 통해 각 돌마다 한 개씩의 유해를 확정짓는 데 성공했습니다. 이들을 특별히 -1번부터 -5번까지 번호를 매겼습니다. $A_i$를 $i$번 조각의 종류라고 하면, $A_{-i}=i$  ($i=1, 2, 3, 4, 5$)가 성립합니다.

당신은 나머지 $N$개의 조각이 어떤 돌의 유해였는지를 알아내기 위해 분석 장치를 사용할 수 있습니다. 분석 장치에 몇 개의 조각을 넣으면, 서로 다른 종류의 유해가 몇 개인지를 알 수 있습니다. 즉, 분석 장치에 넣은 조각 번호의 집합이 $S$라면, 다음 값을 알 수 있습니다. (단, $n(S)$는 집합 $S$의 서로 다른 원소의 수)

$n ( \{ x| \exists y \in S \quad s.t. A_y = x \} ) $

분석 장치를 사용하는 데에는 많은 비용이 들기 때문에, 당신은 분석 장치를 $\lceil \frac{7}{3} N\rceil$번 이하로 사용해 $A_i$의 값을 모두 알아내고자 합니다. 

입력

첫 줄에는 테스트 케이스의 개수 $T$가 주어집니다.

출력

각 테스트 케이스에서 당신이 작성한 프로그램은 채점 프로그램과 아래와 같이 상호작용해야 합니다.

  • 먼저 당신의 프로그램은 입력으로 $N$을 입력받습니다. $N$은 다른 테스트 케이스와 구분되어 한 줄에 하나씩 들어옵니다.
  • 당신은 분석 장치를 사용하기 위해 $?$ $k$ $b_1$ $b_2$ $\cdots$ $b_k$와 같은 줄을 출력해 질문을 할 수 있습니다. $k$는 분석 장치에 넣을 돌의 개수입니다.
  • 당신이 위와 같이 출력할 때마다, 채점 프로그램은 $A_{b_1}, A_{b_2}, \cdots, A_{b_k}$ 중에는 몇 종류의 서로 다른 값이 있는지를 제공합니다. 당신은 정수 하나를 입력받아 채점 프로그램이 알려준 값을 받을 수 있습니다.
  • 만약 돌 조각의 종류를 모두 알아낸 경우, $!$ $A_1$ $A_2$ $\cdots$ $A_N$을 출력해 테스트 케이스를 종료합니다.
  • 각 줄을 출력한 뒤에는 출력 버퍼를 비워야 합니다. (노트 문단 참조)

이해를 돕기 위해 상호작용의 예제를 아래와 같이 첨부합니다. 빈 줄은 실제로 출력하는 것이 아닌, 참가자의 이해를 돕기 위함입니다. 어떤 경우에도 빈 줄을 출력하거나, 빈 줄을 입력받으려고 해서는 안 됩니다.

제한

  • $1 \le N \le 600$
  • $1 \le A_i \le 5$
  • 각 데이터에서 $N$의 합은 600 이하입니다.
  • 그레이더는 적응적이지 않습니다. 즉, 사전에 답을 고정하고, 당신의 질문에 따라서 답을 바꾸지 않습니다.
  • $1 \le k \le N+5$
  • 모든 $1 \le i \le k$인 정수 $i$에 대해, $-5 \le b_i \le -1$ 또는 $1 \le b_i \le N$

예제 입력 1

1
3
 
1
 
1
 

예제 출력 1

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

노트

출력 버퍼를 비우는 방법은 아래와 같습니다.

  • C / C++의 경우: fflush(stdout);
  • python의 경우: sys.stdout.flush()
  • 기타 언어의 경우: 각 언어의 documentation을 참조하세요.

채점 및 기타 정보

  • 예제는 채점하지 않는다.