Description

有一个宽度为 $w$ 高度为 $h$ 的方格纸， $w \times h$ 的格子中，有一些是空的，有一些是洞，有一些是障碍物。从第一行的空的格子中随机选一个放置一个球，向上下左右移动的概率比为 $p_u : p_d : p_l : p_r$（满足 $p_u + p_d + p_l + p_r = 100$），不能移动到有障碍物的格子上。对于每个洞，输出落入该洞的概率。$w \le 20, h \le 10000$。保证第一行没有洞。

Input Format

第一行两个整数表示 $w, h$ 。

第二行四个整数表示 $p_u, p_d, p_l, p_r$ 。

接下来有一个 $h$ 行 $w$ 的字符矩阵，其中 . 表示空，X 表示障碍物，T 表示洞。

Output Format

若干行，每一行一个整数，按照矩阵从上到下，从左到右的顺序，输出每个洞的答案。绝对误差不超过 $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