상자 닫기 II

'상자 닫기(Shut the Box)'는 서로 다른 양의 정수가 적힌 카드들을 한 줄로 놓고 하는 주사위 게임이다. 각 카드는 열려 있거나(앞면) 닫혀 있다(뒷면). 매 차례 주사위를 굴려 나온 합을 확인하고, 열려 있는 카드 중 값의 합이 그 합과 정확히 같은 카드들의 집합을 골라 닫는다. 그런 집합을 만들 수 없으면 그 차례가 끝나고 상자는 닫히지 못한다. 모든 카드를 닫으면 승리한다('상자를 닫았다').

주사위 규칙에는 한 가지 반전이 있다. 보통은 공정한 주사위 두 개를 굴린다(순서를 구분한 36가지 경우가 모두 같은 확률이며 합은 2부터 12까지). 그러나 아직 열려 있는 카드들의 값의 총합이 6 이하이면 공정한 주사위 하나만 굴린다(합은 1부터 6까지, 각 확률 $1/6$).

배너 박사는 상자 닫기에서 계속 지고 있어 곧 이성을 잃기 직전이다. 그를 진정시키려면 최선의 수를 알려 주어야 한다. 즉, 지금 열려 있는 카드들과 방금 굴려 나온 합이 주어졌을 때, 앞으로 최적으로 진행한다고 가정하고 결국 상자를 닫을 확률을 최대로 만드는 '닫을 카드들의 집합'을 골라야 한다. 그리고 그 확률도 함께 보고해야 한다.

예시로, 열려 있는 카드가 1, 2, 3이고 굴려 나온 합이 3이라고 하자. 가능한 수는 두 가지다.

• 1과 2를 닫는다. 카드 3이 남으므로, 상자를 닫으려면 다음 굴림에서(열린 합이 3이므로 주사위 하나) 3이 나와야 한다: 확률 $1/6 \approx 0.1667$.
• 3을 닫는다. 카드 1과 2가 남고, 결국 이들을 닫을 확률은 $\frac{1}{6} + \frac{2}{6}\cdot\frac{1}{6} = \frac{8}{36} \approx 0.2222$ 이다.

두 번째 수가 더 좋으므로 그것이 답이다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다($T < 100$). 이어지는 각 줄은 하나의 테스트 케이스로, 굴려 나온 합(목표값), 열린 카드의 개수 $n$, 그리고 오름차순으로 정렬된 $n$개의 열린 카드 값이 공백으로 구분되어 주어진다.

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

• 열린 카드들 중 합이 목표값과 같은 집합이 하나라도 있으면, 최선의 수를 다음 형식으로 출력한다: The best move is: <카드들>, and probability of shutting = <확률> 여기서 <카드들>은 닫을 카드 값들을 오름차순으로 공백 하나씩 구분해 나열한 것이고, <확률>은 그 수를 둔 뒤 결국 상자를 닫을 확률이다. 확률은 소수점 아래 넷째 자리까지 반올림해 출력하되, 남은 카드를 모두 닫아 확률이 1인 경우에는 정확히 1로 출력한다.
• 합이 목표값과 같은 집합이 없으면 No move found.를 출력한다.

최대 확률이 같은 수가 여러 개이면, 닫을 카드들을 오름차순으로 나열한 목록이 사전순으로 가장 앞서는 것을 고른다.

• $1 \le T < 100$.
• 각 줄의 열린 카드는 서로 다른 양의 정수이며 오름차순으로 주어진다.
• 공정한 주사위 두 개를 사용하되, 열린 카드들의 총합이 6 이하이면 공정한 주사위 하나만 사용한다.