레이팅 미적용당신은 Addictive Coin Machines에 고용되어, 전 세계 카지노를 위한 눈길을 사로잡고(e\(ye-ca\)tching) 동전을 삼키는(co\(in-gu\)zzling), 한 판만 더(ju\(st-one-more-tr\)y)를 외치게 하는 파친코 기계 라인업의 차기 히트작 설계를 돕게 되었다. 파친코 기계는 못, 장애물, 표적으로 가득한 직사각형 격자에 공을 쏘아 넣는 방식으로 진행된다. 공은 격자 안을 이리저리 튕겨 다니다가 결국 표적 중 하나에 부딪힌다. 어느 표적에 맞았는지에 따라 플레이어는 일정 점수를 얻는다. 다음 파친코 기계의 격자 패턴은 이미 설계되었지만 표적들의 점수는 아직 정해지지 않았다. 모든 카지노 기계가 그렇듯 기계가 수익을 내되 너무 많이 내지는 않도록 점수를 정해야 한다. 따라서 공이 특정 표적에 맞을 확률을 알아내는 것이 중요하다. 그것이 당신의 일이다! 단순화를 위해 격자는 대체로 빈 공간(most\(ly-op\)en, 각각 ‘.’로 표현), 통과할 수 없는 장애물(각각 ‘X’로 표현), 표적(각각 ‘T’로 표현)으로 채워진 세로로 긴 직사각형으로 모델링한다. 공은 격자 맨 윗 행의 빈 공간들(most\(ly-op\)en) 중 한 곳으로 균등한 확률로 무작위로 발사된다. 그 이후에는 못과의 충돌로 공이 주어진 확률에 따라 위, 아래, 왼쪽, 오른쪽으로 무작위로 튕긴다. 단순화를 위해 이 확률들은 격자의 모든 칸에서 같다고 가정한다. 공이 장애물로 튕기거나 격자 밖으로 나가려 하면 실제로는 현재 칸에서 움직이지 않는다. 공이 표적으로 이동하면 게임에서 제거된다. 공이 표적에 맞기 전까지 방문하는 칸 수의 평균이 \(10^{9}\)를 넘지 않는다고 가정해도 된다. 공이 영원히 튕겨 다니기만 한다면 그리 즐거운 게임이 되지 못할 것이다! 각 표적에 대해, 발사된 공이 맞히는 표적이 그것일 확률을 계산하시오.
입력은 하나의 테스트 케이스로 이루어져 있다. 첫 줄에는 파친코 격자의 너비와 높이인 정수 \(w\)와 \(h\) (\(1 \le w \le 20\), \(2 \le h \le 10\,000\))가 주어진다. 다음 줄에는 합이 100인 음이 아닌(n\(on-ne\)gative) 네 정수 \(u\), \(d\), \(l\), \(r\)이 주어지며, 이는 빈 칸에서 공이 위, 아래, 왼쪽, 오른쪽으로 튕길 퍼센트 확률이다. 다음 \(h\)개의 줄에는 각각 \(w\)개의 문자가 있고, 각 문자는 ‘.’, ‘X’, ‘T’ 중 하나이다. 이 줄들이 파친코 격자를 설명한다. 격자의 맨 윗 행을 설명하는 첫 줄에는 ‘.’이 적어도 하나 있고 ‘T’는 없다.
격자의 각 ‘T’마다 위에서 아래 순서로, 같은 높이면 왼쪽에서 오른쪽 순서로 한 줄씩 출력한다. 각 표적에 대해 발사된 공이 그 표적을 맞힐 확률을 출력한다. 답의 절대 오차는 \(10^{−}^{6}\) 이하여야 한다.
3 2
20 20 20 40
X.X
T.T
0.333333333
0.666666667
4 5
12 33 28 27
....
.XX.
....
T..T
XTTX
0.435853889
0.403753221
0.081202502
0.079190387