All the action takes place in a rectangular area which, for the sake of
simplicity, is divided into unit squares numbered from
to
.
Starting at
, the knights move from one square to one of the at most four adjacent squares, and
finish as soon as they reach
where the tavern is located.
At each square, it is largely a matter of chance where the fight will continue,
but it also depends on the environment (for example, if a certain direction is
uphill).
Our model uses probabilities to decide into which adjacent square the fight will move
next. (For example, an uphill direction has a lower probability.)
It is your job to calculate the expected number of moves that are needed before
the tavern is reached. You can assume that every move is independent of the
directions chosen in the previous moves.
Input
The input consists of a sequence of rectangular areas.
Each area starts with a line containing the dimensions of the rectangle
and
, where
.
Four blocks follow that state the probability of a move in each direction.
Every block contains
lines, and each line contains
numbers
, where
for all
and
and
.
The probabilities in block
are arranged as follows:
The number
Output
For each area, output a line containing the expected number of moves from
to
. This number must have an absolute error less than
compared to
the exact answer that is always less than
.
Sample Input
Sample Output