$N$명의 사이클리스트 $1, \dots, N$이 있다. 각 사이클리스트는 $1$부터 $N$까지의 서로 다른 실력을 가지고 있으며, 두 사이클리스트가 대결하면 항상 실력이 더 높은 쪽이 승리한다.

사이클리스트들은 경기에 참여하는 것을 좋아한다. 경기에서 사이클리스트들은 원형 리스트 형태로 배치된다. 경기는 라운드 단위로 진행된다. 각 라운드에서 사이클리스트는 자신의 양옆에 있는 이웃들과 경주한다. 만약 양쪽 이웃 모두에게 패배하면 해당 사이클리스트는 탈락한다.

당신은 사이클리스트들의 실력을 알지 못하며, 이를 알아내고자 한다. 당신은 모든 사이클리스트가 참여하는 경기를 열 수 있으며, 매번 원형 리스트에 배치할 순서를 정할 수 있다. 각 경기가 끝날 때마다 어떤 사이클리스트가 몇 번째 라운드에 탈락했는지 알 수 있다.

최적의 경기 횟수를 사용하여 실력을 알아내거나, 부분 점수를 위해 $N$번의 경기를 사용하여 실력을 알아내시오.

인터랙션

각 테스트 케이스는 여러 개의 테스트 사례를 포함한다. 인터랙션은 테스트 케이스의 수인 정수 $T$ ($1 \le T \le 10^4$)가 포함된 줄로 시작한다.

각 테스트 케이스는 사이클리스트의 수인 정수 $N$ ($3 \le N \le 300$)이 포함된 줄로 시작한다.

이후 경기를 열 수 있다. 경기를 열려면 “? $a_1$ $a_2$ $\dots$ $a_n$” 형태의 줄을 출력한다. 여기서 $a_k$는 사이클리스트 리스트의 $k$번째 위치에 있는 사이클리스트를 나타낸다. 리스트 $a_1, \dots, a_n$은 $1, \dots, n$의 순열이어야 한다.

쿼리에 대한 답변은 “$r_1$ $r_2$ $\dots$ $r_n$” 형태의 줄로 주어지며, $r_k$는 $0 \le r_k < n$을 만족한다. $r_k > 0$인 경우, $k$번째 위치에 있던 사이클리스트가 경기의 $r_k$번째 라운드에서 탈락했음을 의미한다. $r_k = 0$이면 해당 사이클리스트가 경기에서 우승했음을 의미한다.

사이클리스트들의 실력을 모두 알아냈다면, “! $s_1$ $s_2$ $\dots$ $s_n$” 형태의 줄을 출력한다. 여기서 $s_k$는 사이클리스트 $k$의 실력과 같아야 한다.

잘못된 쿼리를 보내거나 $N$번을 초과하여 경기를 열려고 시도하면 Wrong Answer 판정을 받는다. 또한, 출력한 실력 집합이 인터랙터가 가진 실력 집합과 다를 경우에도 Wrong Answer 판정을 받는다. 두 경우 모두 인터랙션은 즉시 종료된다. 그렇지 않으면, 채점 섹션에 설명된 대로 점수를 받게 된다.

인터랙터는 적응형(adaptive)일 수 있음에 유의하라. 즉, 사이클리스트의 실제 실력은 인터랙션 도중에 변경될 수 있지만, 현재의 실력 집합은 항상 이전의 모든 경기 결과와 일관성을 유지한다.

채점

각 테스트 케이스에 대해, 당신의 솔루션이 진행한 경기 횟수를 $q$라고 하자. 또한, 각 $N$에 대해 실력을 알아낼 수 있음을 보장하는 최소 경기 횟수를 $c_N$이라고 하자.

모든 테스트 케이스에 대해 $q \le c_N$이면 100점을 받는다. 그렇지 않으면 10점을 받는다. 문제의 제약 조건 하에서 10점을 받기 위해서는 모든 테스트 케이스에 대해 $q \le N$을 만족해야 함에 유의하라.

예제

입력 1

1
5

출력 1

? 1 2 3 4 5

입력 2

3 2 1 0 1
? 1 3 5 2 4

출력 2

3 1 2 1 0
? 1 4 2 5 3

입력 3

3 0 1 2 1
! 4 2 1 5 3

참고

예제에서 사이클리스트들의 실력은 각각 4, 2, 1, 5, 3이다.

첫 번째 경기에서 사이클리스트들은 [1, 2, 3, 4, 5] 순서로 배치된다. 경기는 다음과 같이 진행된다. (각 라운드에서 탈락한 사이클리스트는 X로 표시됨)

• 1라운드:

  • 3번 위치의 사이클리스트(실력 1)는 2번 및 4번 위치의 사이클리스트(실력 2, 5)에게 패배하여 탈락한다.
  • 5번 위치의 사이클리스트(실력 3)는 4번 및 1번 위치의 사이클리스트(실력 5, 4)에게 패배하여 탈락한다.
  • 1번 위치의 사이클리스트(실력 4)는 5번 및 2번 위치의 사이클리스트(실력 3, 2)를 이겨서 탈락하지 않는다.
  • 2번 위치의 사이클리스트(실력 2)는 3번 위치의 사이클리스트(실력 1)를 이겨서 탈락하지 않는다.
  • 4번 위치의 사이클리스트(실력 5)는 3번 및 5번 위치의 사이클리스트(실력 1, 3)를 이겨서 탈락하지 않는다.

• 2라운드에서 사이클리스트 리스트는 [1, 2, X, 4, X]이다.

  • 2번 위치의 사이클리스트는 1번 및 4번 위치의 사이클리스트에게 패배하여 탈락한다.
  • 1번 위치의 사이클리스트는 2번 위치의 사이클리스트를 이겨서 탈락하지 않는다.
  • 4번 위치의 사이클리스트는 나머지 두 사이클리스트를 이겨서 탈락하지 않는다.

• 3라운드에서 사이클리스트 리스트는 [1, X, X, 4, X]이다.

  • 1번 위치의 사이클리스트는 4번 위치의 사이클리스트에게 패배하여 탈락한다.
  • 4번 위치의 사이클리스트는 1번 위치의 사이클리스트를 이겨서 탈락하지 않는다.

따라서, 1번 위치의 사이클리스트는 3라운드에 탈락했다. 2번 위치의 사이클리스트는 2라운드에 탈락했다. 3번 위치의 사이클리스트는 1라운드에 탈락했다. 4번 위치의 사이클리스트가 우승했다. * 5번 위치의 사이클리스트는 1라운드에 탈락했다.

쿼리에 대한 답변은 [3, 2, 1, 0, 1]이 된다.

두 번째 경기에서 사이클리스트들은 [1, 3, 5, 2, 4] 순서로 배치된다. 경기는 다음과 같이 진행된다.

• 1라운드:

  • 2번 위치의 사이클리스트(실력 1)는 1번 및 3번 위치의 사이클리스트(실력 4, 3)에게 패배하여 탈락한다.
  • 4번 위치의 사이클리스트(실력 2)는 3번 및 5번 위치의 사이클리스트(실력 3, 5)에게 패배하여 탈락한다.
  • 1번 위치의 사이클리스트(실력 4)는 2번 위치의 사이클리스트(실력 1)를 이겨서 탈락하지 않는다.
  • 3번 위치의 사이클리스트(실력 3)는 2번 및 4번 위치의 사이클리스트(실력 1, 2)를 이겨서 탈락하지 않는다.
  • 5번 위치의 사이클리스트(실력 5)는 4번 및 1번 위치의 사이클리스트(실력 2, 4)를 이겨서 탈락하지 않는다.

• 2라운드에서 사이클리스트 리스트는 [1, X, 5, X, 4]이다.

  • 3번 위치의 사이클리스트는 1번 및 5번 위치의 사이클리스트에게 패배하여 탈락한다.
  • 1번 위치의 사이클리스트는 3번 위치의 사이클리스트를 이겨서 탈락하지 않는다.
  • 5번 위치의 사이클리스트는 나머지 두 사이클리스트를 이겨서 탈락하지 않는다.

• 3라운드에서 사이클리스트 리스트는 [1, X, X, X, 4]이다.

  • 1번 위치의 사이클리스트는 5번 위치의 사이클리스트에게 패배하여 탈락한다.
  • 5번 위치의 사이클리스트는 1번 위치의 사이클리스트를 이겨서 탈락하지 않는다.

따라서, 1번 위치의 사이클리스트는 3라운드에 탈락했다. 2번 위치의 사이클리스트는 1라운드에 탈락했다. 3번 위치의 사이클리스트는 2라운드에 탈락했다. 4번 위치의 사이클리스트는 1라운드에 탈락했다. * 5번 위치의 사이클리스트가 우승했다.

쿼리에 대한 답변은 [3, 1, 2, 1, 0]이 된다.