보드게임

Bahu는 Bala와 보드게임을 하고 있다. 각 플레이어는 다양한 전투력 값을 가진 3 * N장의 군대 카드를 가지고 있다. 게임에는 3개의 전장이 있다. 각 플레이어는 각 전장에 자신의 카드가 정확히 N장씩 배정되도록 카드를 뒷면이 보이게 전장들에 분배해야 한다.

게임이 시작되면 모든 카드가 공개된다. 각 전장에서 각 플레이어는 그 전장에 놓인 자신의 N장 카드의 전투력 값을 합산한 다음, 두 플레이어가 그 합계를 비교한다. 한 플레이어의 합계가 더 높으면 그 플레이어가 해당 전장에서 승리한다. 합계가 같으면 Bala가 해당 전장에서 승리하며, 이는 Bala의 특별한 이점이다.

게임의 최종 승자는 더 많은 전장에서 승리한 플레이어이다. (전장이 3개이므로 최종적으로 무승부가 되지 않음이 보장된다.)

Bala는 자신의 이점만으로도 이길 수 있다고 생각하므로, 자신의 카드를 무작위로 섞은 뒤 처음 N장은 첫 번째 전장에, 다음 N장은 두 번째 전장에, 마지막 N장은 세 번째 전장에 놓는다.

Bahu는 불리한 상황에서도 승리하려고 한다! Bahu가 자신의 카드를 최적으로 분배할 때 승리할 확률을 구한다. Bala의 모든 카드는 뒷면이 보이므로 Bahu는 Bala의 카드 분배를 보기 전에 자신의 카드 분배를 선택해야 한다는 점에 유의한다.

제한

1 ≤ T ≤ 100. 시간 제한: 테스트 세트당 60초. 메모리 제한: 1 GB. 모든 i에 대해, 1 ≤ $A_{i}$ ≤ $10^{6}$. 모든 i에 대해, 1 ≤ $B_{i}$ ≤ $10^{6}$.

작은 데이터 세트 (테스트 세트 1 - 공개)

N = 3.

큰 데이터 세트 (테스트 세트 2 - 비공개)

3 ≤ N ≤ 5.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어지며, 각 테스트 케이스는 세 줄로 구성된다. 첫 번째 줄에는 위에서 설명한 정수 N이 주어진다. 두 번째 줄에는 Bahu의 카드 전투력 값을 나타내는 3 * N개의 정수 $A_{0}$, $A_{1}$, ... , $A_{3*N-1}$이 주어진다. 세 번째 줄에는 Bala의 카드 전투력 값을 나타내는 3 * N개의 정수 $B_{0}$, $B_{1}$, ... , $B_{3*N-1}$이 주어진다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x은 테스트 케이스 번호이며 1부터 시작하고, y은 위에서 설명한 확률이다. y의 절대 오차 또는 상대 오차가 정답의 10^{-6} 이내이면 정답으로 간주한다. 이것이 무엇을 의미하는지와 허용되는 실수 형식에 대한 설명은 FAQ을 참조한다.

예제 케이스 #1에서 Bahu는 첫 번째 전장에 카드 (2, 2, 2), 두 번째 전장에 카드 (2, 2, 3), 세 번째 전장에 카드 (2, 2, 3)를 놓을 수 있다. Bala의 모든 카드가 2이므로 Bala는 첫 번째 전장에서 승리하고 Bahu는 두 번째와 세 번째 전장에서 승리한다.