Pachinko

카지노용 Pachinko 격자가 있습니다. 격자 칸은 빈 칸(.), 장애물(X), 목표(T) 중 하나입니다.

공은 맨 윗줄의 빈 칸 중 하나에 균등하게 발사됩니다. 빈 칸에서 공은 상, 하, 좌, 우로 각각 주어진 확률(합 100%)로 튀며, 장애물이나 격자 밖으로 가려 하면 제자리에 남습니다. 목표 칸에 들어가면 멈춥니다.

각 목표 T에 대해, 발사된 공이 그 목표에 도달할 확률을 구하세요. 목표는 위에서 아래, 같은 줄에서는 왼쪽에서 오른쪽 순으로 출력합니다. 절대 오차 $10^{-6}$ 이내.

• 1번째 줄: $w$, $h$ ($1 \le w \le 20$, $2 \le h \le 10\,000$).
• 2번째 줄: $u$, $d$, $l$, $r$ (합 100).
• 다음 $h$줄: 격자. 맨 윗줄에 .가 하나 이상, T는 없음.

각 T마다 확률을 한 줄씩 (소수 9자리 권장).