Problem Description

Justin and Donald are playing a game called Checkers. You might not have heard of it, but the rules are very simple.

The board is a rectangular grid, and at the beginning, each cell has exactly one piece, with each player having at least one piece on the board. Justin's pieces are marked as J, and Donald's are marked as D.

Justin moves first. In a move, a player can move one of their pieces and capture an adjacent piece (not necessarily the opponent's), after which it's the opponent's turn. If the current player cannot make such a move, they lose.

Pieces $A$ and $B$ are adjacent if and only if $A$ is exactly one cell above, below, left, or right of $B$.

In an ideal world, both are excellent logicians and can know the best strategy for every board state. However, this is unrealistic. In fact, during play, both will only choose relatively good moves. How good these moves are depends on Justin and Donald's error constants, which are $J$ and $D$ respectively.

Formally, a player with error constant $A$ will choose $A$ moves from all possible moves to form a set of move plans. If the number of possible moves $P \le A$, then the set only contains these $P$ moves. Then, the player will randomly (with equal probability) select one from this set and make the move accordingly.

Both players always choose the optimal moves when forming the set of move plans, knowing that the opponent will also choose the optimal moves.

What is the probability that Justin wins?

Input Format

The first line contains two positive integers, $R$ and $C$ (separated by a space).

The next $R$ lines, each containing $C$ characters, represent the initial distribution of pieces on the board (as described in the problem statement).

The last line contains two positive integers, $J$ and $D$ (separated by a space), as described in the problem statement.

Output Format

One line containing a floating-point number accurate to three decimal places, representing the probability of Justin winning.

Sample Input and Output

Sample Input #1

1 3
JJD
3 1

Sample Output #1

0.667

Sample Input #2

2 2
JJ
DD
3 1

Sample Output #2

0.000

Notes

Constraints

$1 \le R \times C \le 13$

$1 \le J, D \le 13$

The initial board distribution only uses the characters J and D.

Sample Explanation

Sample 1:

Justin has 3 possible moves, resulting in the following board states (with _ representing an empty cell):

_JD (first piece moves right), J_J (second piece moves right), J_D (second piece moves left).

For case 1, Justin loses. For cases 2 and 3, Justin wins. Since Justin's error constant is 3, he will choose all cases, so the win rate is $\frac{2}{3}$, rounded to 0.667.

Sample 2:

Justin has 4 possible moves, resulting in the following board states (with _ representing an empty cell):

J_ _J J_ _J
DD DD DJ JD

However, no matter which move Justin chooses, he cannot win.

Then Donald will choose the optimal move. He can choose the following moves to defeat Justin:

D_ _D J_ _J
_D D_ _D D_

Thus, Justin cannot win.

见题面 Input 部分

见题面 Output 部分