Pachinko Probability Calculation

You have been hired by Addictive Coin Machines to help design the next hit Pachinko machine. The machine is represented by a rectangular grid of . (open spaces), X (obstacles) and T (targets). A ball is launched uniformly at random into one of the open spaces in the top row. At every step the ball bounces in one of the four directions: up, down, left, or right. The probability of bouncing in a given direction is given by p_up, p_down, p_left, and p_right (with \(p_{up}+p_{down}+p_{left}+p_{right}=1\)).

If the ball attempts to move off the grid or into an obstacle, it will not move, and that move counts as a bounce. Once the ball enters a target cell it is immediately absorbed and removed from play. It is guaranteed that the expected number of moves before absorption does not exceed \(10^9\).

Your task is to compute, for each target (in the order they appear in the grid when read row‐by‐row from top to bottom and left to right), the probability that a ball launched as described will eventually hit that target. Note that only open spaces (i.e. .) in the top row are valid launching positions.

inputFormat

The input begins with a line containing two integers n and m denoting the number of rows and columns respectively.

This is followed by n lines, each containing exactly m characters. The characters can be . (open space), X (obstacle), or T (target).

The last line of input contains four space‐separated real numbers: p_up p_down p_left p_right, which are the probabilities for the ball to bounce in the up, down, left, and right directions, respectively.

outputFormat

For each target (in row‐major order), output a line with the probability that a ball will eventually hit that target. Output the probabilities with at least 9 decimal places of precision.

sample

2 2
.T
TT
0.25 0.25 0.25 0.25

0.500000000
0.500000000
0.000000000