The Drunken Walk

Alice has observed that when people are in a bad mood they tend to drink heavily. Unlike the exuberant celebrations by OI competitors after a win, the drunken person loses his way and wanders randomly along the city streets, muttering incomprehensible words.

Recently, Bob has been in a bad mood because of exams. Every night he visits a bar in the city. After getting drunk he leaves the bar and wanders randomly through the city streets until, by chance, he meets Alice who is out stargazing. When that happens, she takes him home.

The city is represented by a grid of points with N rows and M columns. The intersections (or crossroads) are labelled \((i,j)\) with \(0 \le i \le N-1\) and \(0 \le j \le M-1\). Between intersections there are bidirectional roads. Specifically, for every \(0 \le i \le N-2\) and \(0 \le j \le M-1\) there is a vertical road connecting \((i,j)\) and \((i+1,j)\) with travel time cost \(p_{(i,j)}\). Similarly, for every \(0 \le i \le N-1\) and \(0 \le j \le M-2\) there is a horizontal road connecting \((i,j)\) and \((i,j+1))\) with travel time cost \(q_{(i,j)}\).

Given two points \((u,v)\) and \((s,t)\) representing, respectively, the bar Bob visits and the place where Alice is stargazing, Bob leaves the bar and at each intersection chooses one of the available adjacent intersections with equal probability. Note that even if Bob just came from a certain intersection, he might immediately go back, and his previous path does not influence his future decisions. (For example, if Bob goes from \((3,4)\) to \((3,5)\), he might choose to go back to \((3,4)\) next.)

Your task is to compute the expected time until Bob reaches \((s,t)\) starting from \((u,v)\). The expected time \(E(i,j)\) for any intersection (except \((s,t)\)) is governed by the equation

[ E(i,j) = \frac{1}{d(i,j)}\sum_{(i,j)\to (k,\ell)} \Big(\text{cost}_{(i,j)\to (k,\ell)} + E(k,\ell)\Big), ]

where \(d(i,j)\) is the number of neighbors of \((i,j)\). For the target \((s,t)\) we have \(E(s,t)=0\).

inputFormat

The input begins with two integers \(N\) and \(M\) representing the number of rows and columns of the grid.

This is followed by \(N-1\) lines, each containing \(M\) integers. The \(j\)-th integer in the \(i\)-th line denotes \(p_{(i,j)}\), the cost to travel from \((i,j)\) to \((i+1,j)\) (and vice versa).

Then there are \(N\) lines, each containing \(M-1\) integers. The \(j\)-th integer in the \(i\)-th line denotes \(q_{(i,j)}\), the cost to travel from \((i,j)\) to \((i,j+1))\) (and vice versa).

The last line contains four integers: \(u\), \(v\), \(s\), and \(t\), which represent the starting intersection (the bar Bob visits) and the target intersection (where Alice is), respectively.

outputFormat

Output a single number: the expected time (in the same time units as the costs) that Bob will take to reach \((s,t)\) from \((u,v)\). The answer should be printed with at least 6 digits after the decimal point.

sample

2 2
1 2
3
4
0 0 1 1

9.000000