샷 더 박스 I

컬렉터를 쫓던 어벤져스는 은하를 가로지르는 긴 여정에 올랐고, 우주선 안에서 시간을 보낼 방법을 찾고 있다. 그러다 예전 뱃사람들 사이에서 인기 있던 샷 더 박스(Shut the Box) 라는 오래된 게임을 발견한다.

각 플레이어는 $1$부터 $9$까지 번호가 적힌 카드 9장을 숫자가 보이도록 앞면으로 펼쳐 놓고 시작하며, 더 이상 움직일 수 없을 때까지 게임을 진행한다.

게임은 주사위 두 개로 진행하되, 펼쳐진(앞면인) 카드의 합이 $6$ 이하이면 주사위를 하나만 사용한다는 규칙이 있다. 처음에는 모든 카드가 앞면이다. 플레이어가 주사위를 굴려 나온 합을 $m$이라 하자. 플레이어는 앞면인 카드 중 값의 합이 정확히 $m$인 집합을 하나 골라 뒤집어(닫아) 놓는다.

예를 들어 첫 턴에 $6$과 $2$가 나와 합이 $8$이면, 카드 $8$ 하나를 닫거나, 카드 $1$과 $7$을, 또는 $2$와 $6$을, 또는 세 장 $1, 2, 5$를 닫을 수 있다. 또 다른 예로 앞면인 카드가 $1, 2, 6$인데 $4$가 나오면 합이 $4$가 되는 카드 집합이 없으므로 아무 카드도 닫을 수 없고 턴이 끝난다.

최종 점수는 여전히 앞면으로 남아 있는 카드들의 합이며, 목표는 이 점수를 최대한 낮추는 것이다(가장 이상적으로는 "상자를 닫아" 남은 앞면 카드를 하나도 남기지 않는 것). 위에서 $1, 2, 6$이 앞면으로 남은 채 끝났다면 최종 점수는 $1 + 2 + 6 = 9$이다.

그림 1: 두 가지 경우에 대한 샷 더 박스 게임 예시(오른쪽 예시는 마지막 몇 수만 보여 준다). 펼쳐진 카드의 합이 $6$ 이하일 때는 주사위를 하나만 사용한다(오른쪽 예시).

배너 박사(헐크)는 다음 전략을 따른다. 이번에 나온 주사위 합에 대해 닫을 수 있는 모든 유효한 카드 집합을 생각한다.

• 유효한 집합이 하나뿐이면 그것을 택한다.
• 여러 개라면 가장 작은 카드 값이 가장 큰 집합을 택한다. 예를 들어 $\{1, 7\}$과 $\{2, 6\}$ 중에서는 $\{2, 6\}$을 택한다.
• 가장 작은 값이 같아 여전히 여러 개라면, 두 번째로 작은 값이 가장 큰 집합을 택한다. 예를 들어 $\{2, 4, 6\}$과 $\{2, 3, 7\}$ 중에서는 $\{2, 4, 6\}$을 택한다.

일반적으로, 유효한 집합들 중 카드 값을 오름차순으로 나열한 수열이 사전순으로 가장 큰 것을 택한다.

배너 박사를 대신해 이 선택을 해 주는 프로그램을 작성하라(헐크를 화나게 하면 어떻게 되는지 알 것이다).

첫 번째 줄에는 테스트 케이스의 수 $T$가 주어진다($T < 100$).

이어지는 $T$개의 줄은 각각 하나의 테스트 케이스를 나타낸다. 각 줄은 주사위로 나온 합(target)으로 시작하고, 그 뒤에 앞면인 카드의 개수 $n$, 그리고 앞면인 카드 $n$개의 값이 오름차순으로 이어진다.

각 테스트 케이스마다 한 줄을 출력한다.

유효한 수가 하나라도 있으면 위 전략에 따른 최선의 수를 다음 형식으로 정확히 출력한다.

The best move is: c1 c2 ... ck

여기서 $c_1, c_2, \dots, c_k$는 선택한 카드 값을 오름차순으로 나열한 것이며, 하나의 공백으로 구분한다.

앞면인 카드의 어떤 집합도 합이 target이 되지 않으면 다음을 정확히 출력한다.

No move found.