모두 살아남았는가?

당신은 친구들과 1인칭 슈팅 게임을 하고 있다. 이 게임에서는 $n$명의 플레이어가 두 팀으로 나뉘어 서로 싸운다. 각 플레이어는 머리 위에 풍선을 달고 있으며, 플레이어들은 상대 팀 플레이어의 풍선을 터뜨리려고 한다.

플레이어에게는 1부터 $n$까지 번호가 붙는다. 이 번호를 행동 순서라고 한다. 각 플레이어에게는 명중 확률이라는 실수도 주어진다. 게임은 $n$개의 단계로 진행된다. $i$번째($i = 1, \dots, n$) 단계에서는 행동 순서가 $i$인 플레이어(공격자)가 다음 행동을 한다.

• 공격자의 풍선이 이미 터졌다면 공격자는 사망 상태이며, 이 단계는 아무 행동 없이 넘어간다.
• 상대 팀 플레이어가 모두 사망했다면 이 단계도 넘어간다.
• 그 밖의 경우에는 살아 있는 상대 팀 플레이어 중 한 명을 공격 대상으로 고른다. 대상은 이전 행동의 결과에 따라 고를 수 있다. 공격은 대상과 관계없이 공격자의 명중 확률에 따라 성공한다. 공격이 성공하면 대상의 풍선이 터지고 대상은 사망한다.

모든 단계가 끝나면 게임이 끝난다.

당신은 자기 팀 플레이어가 한 명도 죽지 않기를 바란다. 공격 대상을 최적으로 골랐을 때, 게임이 끝날 때까지 자기 팀 플레이어 전원이 살아남을 확률을 구하라. 상대 팀 플레이어는 공격 대상을 무작위로 고른다고 가정한다.

입력은 여러 개의 데이터셋으로 이루어진다. 데이터셋의 수는 50을 넘지 않는다. 각 데이터셋은 다음 형식으로 주어진다.

$n$ $s_1$ $p_1$ $\vdots$ $s_n$ $p_n$

$n$은 플레이어의 수이며 2 이상 300 이하의 정수이다. 각 $i = 1, \dots, n$에 대해 $s_i$는 "Ally" 또는 "Enemy"이며, 행동 순서가 $i$인 플레이어가 자기 팀이면 Ally, 상대 팀이면 Enemy이다. $p_i$는 명중 확률이며 0 이상 1 이하의 실수이고 소수점 아래 9자리로 주어진다. 두 팀에는 각각 적어도 한 명의 플레이어가 있다.

입력의 끝은 0이 적힌 한 줄로 표시된다.

각 데이터셋에 대해, 공격 대상을 최적으로 골랐을 때 자기 팀 플레이어 전원이 살아남을 확률을 한 줄에 출력한다. 절대 오차 또는 상대 오차가 $10^{-9}$ 이하이면 정답으로 인정한다.