시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 364 84 54 30.857%

문제

전설에 따르면 주사위야말로 진정한 실력을 판가름할 수 있는 도구라고 한다. 그 중 1부터 6까지의 수가 적혀있는 정육면체 주사위가 그 중에서도 으뜸이라고 전해진다. 정육면체 주사위를 던졌을 때 각 면이 나올 확률은 1/6로 같다. 상헌이는 주사위의 시험을 받게 되었다. 정육면체 주사위 N개를 던져, 나온 눈의 합이 K 이상이 되어야 한다.

그러나 상헌이는 주사위 컨트롤 실력이 아직 부족하므로, 주사위 N개를 던진 다음 마음에 안 드는 주사위들을 선택해서 다시 한 번 던질 수 있는 기회를 얻었다. 여기서 어느 주사위도 던지지 않아도 괜찮다.

상헌이는 고민이 든다. 어떤 주사위를 선택해야 모든 눈의 합이 K 이상이 될 확률이 가장 높을까? 상헌이는 실력을 판가름하기 앞서 확률을 계산해보기 위해 여러분들에게 도움을 청했다.

입력

입력의 첫 줄에는 테스트 케이스의 개수를 의미하는 정수 T가 주어진다. (1 ≤ T ≤ 1,000)

각 테스트 케이스는 두 줄로 이루어져 있으며 테스트 케이스 사이에 빈 줄은 없다.

각 테스트 케이스의 첫째 줄에는 상헌이가 가지고 있는 정육면체 주사위의 개수와 눈의 합의 최소 목표치를 의미하는 두 정수 NK가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 20, N ≤ K6N)

각 테스트 케이스의 둘째 줄에는 N개의 정수 a1, a2, ..., aN이 공백으로 구분되어 주어진다. aii 번째 정육면체 주사위를 던져서 나온 눈을 의미하며, 1 이상 6 이하의 자연수이다.

출력

출력은 각 테스트 케이스별로 두 줄로 이루어진다. 그러므로 총 2T개의 줄에 걸쳐서 출력을 해야 한다. 각 테스트 케이스 별로 정육면체 주사위를 적절히 선택해서 다시 던진 후, 모든 눈의 합이 K 이상이 될 확률의 최댓값이 p라고 하자.

각 테스트 케이스마다 첫째 줄에는 정수 6N × 를 출력한다. 이 값은 32비트 정수에 들어가기에는 매우 클 수 있다.

각 테스트 케이스 별로 둘째 줄에는 어떻게 선택해서 던져야 위의 확률 p가 나오는지를 의미하는 N개의 정수 x1, x2, ..., xN 을 공백으로 구분하여 출력한다. xi 는 i 번째 정육면체 주사위를 던져야 하는 경우 1이며 그렇지 않을 경우 0이다. 확률이 p가 되게 정육면체 주사위를 선택할 수 있는 방법이 다양하다면 그중 아무 것이나 출력해도 좋다.

서브태스크 1 (100점)

N ≤ 3을 만족한다.

서브태스크 2 (300점)

문제 입력에서 주어진 조건 외에 추가적인 조건이 없다.

예제 입력 1

3
1 5
3
2 10
6 1
3 8
2 5 4

예제 출력 1

2
1
18
0 1
216
1 0 0

첫 번째 테스트 케이스에서는 주사위를 다시 굴리지 않으면 눈의 합이 5 이상이 될 확률이 0이며, 굴리면 1/3이다.

두 번째 테스트 케이스에서는 두 번째 주사위만 굴리는 것이 최적이며 이 때의 확률은 1/2이다.

세 번째 테스트 케이스에서는 이미 눈의 합이 11이다. 첫 번째 주사위를 굴린 결과와 상관없이 눈의 합이 8 이상이므로 확률은 1이다.

채점

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