Alice has discovered that when people are in a bad mood, they often choose to drink heavily. This is quite different from the jubilant celebrations of OI contestants after winning a competition; once drunk, the alcoholic forgets the way home and wanders aimlessly through the streets, shouting things that no one can understand.

In recent days, Bob has been in a very bad mood due to exams, and every night he finds a bar in the city. After getting drunk and leaving the bar, he begins to wander aimlessly through the city streets until, at some point, he happens to meet Alice, who is out stargazing at night, and she takes him home.

The city streets where Alice and Bob are located can be described as an $N \times M$ grid map, where the $N$ rows are numbered from $0$ to $N-1$ and the $M$ columns are numbered from $0$ to $M-1$. There are $N \times M$ intersections in the city, and each intersection can be represented by coordinates $(i, j)$. If $i < N-1$, there is an undirected edge between $(i, j)$ and $(i+1, j)$ with edge weight $p[i][j]$, representing the time required to traverse this road. If $j < M-1$, there is an undirected edge between $(i, j)$ and $(i, j+1)$ with edge weight $q[i][j]$.

For two given points $(u, v)$ and $(s, t)$, which are the location of the bar Bob visits tonight and the location where Alice is stargazing, respectively: after leaving the bar, at every intersection, Bob chooses one of the available directions with equal probability and walks to the next intersection. Bob does not turn back before reaching the next intersection. At the same time, Bob's future path is not affected by the roads he has traveled previously.

Specifically: if Bob walks from $(3, 4)$ to $(3, 5)$, he may immediately turn back to $(3, 4)$ upon arriving at $(3, 5)$. For a four-way intersection, the probability of Bob walking in any direction is $1/4$; for a three-way intersection (which only exists on the city boundaries), it is $1/3$; and for a two-way intersection (which only exists at the $4$ corners of the city), it is $1/2$.

Alice wants to know, from the moment Bob leaves the bar, how much longer she can expect to wait for Bob. That is, for two given points $(u, v)$ and $(s, t)$, what is the expected time for Bob to walk from $(u, v)$ to $(s, t)$?

Input

The first line contains $N$ and $M$. The next $N-1$ lines each contain $M$ positive integers, where the $j$-th integer in the $i$-th line is $p[i][j]$. The next $N$ lines each contain $M-1$ positive integers, where the $j$-th integer in the $i$-th line is $q[i][j]$. A single line contains an integer $Q$, representing the total number of queries. The next $Q$ lines each contain $4$ integers $u, v, s, t$.

Output

There are $Q$ lines in total, each corresponding to a query: what is the expected distance for Bob to walk from $(u, v)$ to $(s, t)$? Your answer can have any number of decimal places, but it is considered correct only if the error rate is within $0.1\%$ of the correct answer.

Examples

Input 1

2 2
1 2
3
4
4
0 0 0 1
1 0 0 1
1 1 0 1
0 1 1 0

Output 1

7.0000
10.0000
8.0000
10.0000

Subtasks

For $10\%$ of the data, $N \times M \le 25$. For $30\%$ of the data, $N \times M \le 625$. For $50\%$ of the data, $N \times M \le 2500$. For $100\%$ of the data, $N \times M \le 10000$, $Q \le 100$. $p[i][j]$ and $q[i][j] \le 200$. Additionally, there exists $10\%$ of the data where $\min\{N, M\} \le 10$.