Pachinko

Time limit6sMemory limit512 MB

Summary

A ball wanders a grid with random moves and absorbing targets, and each target needs its hit probability from a uniform top-row start.

Level: Hard8 of 10
Topics: Probability, Graph, Matrix
Solved: No attempts yet

Problem

A Pachinko grid uses open cells (.), obstacles (X), and targets (T).

A ball launches uniformly into one open cell on the top row. From an open cell it bounces up, down, left, or right with given percentage probabilities that sum to 100. If a bounce hits an obstacle or leaves the grid, the ball stays put. A target absorbs the ball.

For each target T, output the probability that a launched ball hits it. List targets from top to bottom, breaking ties left to right. Absolute error at most $10^{-6}$ .

Input

Line 1: $w$ , $h$ ( $1 \le w \le 20$ , $2 \le h \le 10\,000$ ).
Line 2: $u$ , $d$ , $l$ , $r$ summing to 100.
Next $h$ lines: the grid. Top row has at least one . and no T.

Output

One probability per target, one line each.

Examples5

Example 1

Input

3 2
20 20 20 40
X.X
T.T

Expected output

0.333333333
0.666666667

Example 2

Input

3 3
25 25 25 25
...
.X.
TTT

Expected output

0.500000000
0.000000000
0.500000000

Example 3

Input

4 4
10 40 25 25
X...
....
XXTT
TX..

Expected output

0.565318818
0.434681182
0.000000000

Example 4

Input

5 5
20 30 20 30
..XX.
.....
.....
TT.T.
XX...

Expected output

0.174729989
0.264923012
0.560346999

Example 5

Input

6 6
15 35 25 25
.....X
X.....
......
...X..
.X....
.TTT..

Expected output

0.244281753
0.285075395
0.470642852