ARAM (작은 입력)

League of Legends에는 "ARAM"(All Random, All Mid)이라는 모드가 있다. 이 문제는 그 규칙을 본떴고, 게임을 해 본 적이 없어도 이해할 수 있다.

한 판을 시작할 때마다 $N$명의 챔피언 중 한 명이 균등한 확률로 배정된다. 챔피언마다 이길 확률이 다르므로 운이 나쁘면 다른 챔피언을 받고 싶어진다. 이럴 때 쓰라고 다시 뽑기 기능이 있다.

다시 뽑기는 일종의 화폐처럼 동작한다. 첫 판을 시작하기 전에 $R$ RD(reroll dollar)를 들고 시작한다. RD가 1 이상일 때만 다시 뽑을 수 있고, 한 번 뽑을 때마다 1 RD를 쓴다. 한 판이 끝날 때마다 $1/G$ RD를 얻는다. 여기서 $G$는 정수다. 다만 잔액은 절대 $R$을 넘지 않는다. $R$ RD를 들고 한 판을 하면 그 판이 끝난 뒤에도 잔액은 여전히 $R$ RD다.

RD가 1 이상일 때 다시 뽑기를 고르면 1 RD를 쓰고 $N$명 중 한 명을 다시 균등한 확률로 배정받는다. 방금 들고 있던 챔피언이 또 나오기도 한다. 새로 받은 챔피언도 마음에 들지 않고 RD가 아직 1 이상 남아 있으면 또 뽑는다. RD가 1 이상인 동안에는 몇 번이든 다시 뽑을 수 있다.

예를 들어 $R = 2$, $G = 2$라고 하자. 첫 판에서 다시 뽑기를 한 번 썼다면 그 판이 끝난 뒤 잔액은 1.5 RD다. 다음 판을 다시 뽑기 없이 끝내면 잔액은 2.0 RD가 된다. 그다음 판도 다시 뽑기 없이 끝내면 잔액은 그대로 2.0 RD인데, 잔액이 $R = 2$를 넘지 않기 때문이다. 그다음 판에서 다시 뽑기를 두 번 쓰면 그 판이 끝난 뒤 잔액은 0.5 RD다.

챔피언 목록과 각 챔피언으로 한 판을 했을 때 이길 확률이 주어진다. $10^{100}$판을 하면서 전략을 최적으로 세울 때 이길 것으로 기대되는 판의 비율을 구하라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 공백으로 구분된 정수 $N$, $R$, $G$가 주어진다. 다음 줄에는 공백으로 구분된 실수 $P_1, P_2, \ldots, P_N$이 주어진다. $P_i$는 $i$번 챔피언으로 한 판을 했을 때 이길 확률이다.

$1 \le T \le 100$, $1 \le N \le 1000$, $1 \le R \le 4$, $1 \le G \le 4$이다. 각 $P_i$는 소수점 아래 넷째 자리까지 적혀 있고 $0 \le P_i \le 1$을 만족한다.

각 테스트 케이스마다 "Case #x: y" 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 최적 전략으로 $10^{100}$판을 했을 때 이기는 판의 비율이다. $y$는 소수점 아래 아홉째 자리까지 반올림해 아홉 자리를 모두 출력한다.

League of Legends는 Riot Games의 상표다. Riot Games는 이 문제와 무관하다.