Description

$\text{Alice}$ finds that when people are in a bad mood, they tend to drink heavily. Unlike the jubilant celebration after an $\text{OI}$ contestant’s victory, a drunkard often forgets the way home and wanders randomly around the streets, shouting incomprehensible words.

These days, $\text{Bob}$ is in a bad mood due to exams. Every night he finds a bar in the city. After getting drunk and leaving the bar, he begins to wander randomly through the city streets until, at some moment, if he happens to meet $\text{Alice}$ who is out watching the stars at night, she will take him home.

The city streets where $\text{Alice}$ and $\text{Bob}$ live can be modeled as a grid of $N$ rows and $M$ columns. Rows are numbered from $0$ to $N - 1$, and columns from $0$ to $M - 1$. There are $N \times M$ intersections in total, and each intersection is denoted by coordinates $(i, j)$. If $i < N - 1$, then $(i, j)$ and $(i + 1, j)$ are connected by an undirected edge whose length is $p_{(i,j)}$, representing the time needed to traverse this road. If $j < M - 1$, then $(i, j)$ and $(i, j + 1)$ are connected by an undirected edge whose length is $q_{(i,j)}$.

Given two points $(u, v)$ and $(s, t)$, which are the locations of the bar that $\text{Bob}$ visits tonight and the place where $\text{Alice}$ watches the stars tonight, respectively. After leaving the bar, at each intersection, $\text{Bob}$ will choose uniformly at random one of the adjacent intersections and then move to it. Before reaching the next intersection, $\text{Bob}$ will not turn back mid-edge. Also, $\text{Bob}$’s future movement is not affected by the roads he has previously taken.

Specifically: if $\text{Bob}$ moves from $(3, 4)$ to $(3, 5)$, he may immediately return to $(3, 4)$ after arriving at $(3, 5)$. At a four-way intersection, $\text{Bob}$ moves in each direction with probability $1/4$; at a three-way intersection (only on the boundary), with probability $1/3$ for each; at a two-way intersection (only at the four corners), with probability $1/2$ for each.

$\text{Alice}$ wants to know, starting from when $\text{Bob}$ leaves the bar, how long she expects to wait until meeting $\text{Bob}$. That is, for the given points $(u, v)$ and $(s, t)$, what is the expected time for $\text{Bob}$ to go from $(u, v)$ to $(s, t)$?

Input Format

The first line contains $N$, $M$.

Then there are $N - 1$ lines, each containing $M$ positive integers, where the entry in row $i$ and column $j$ is $p_{(i,j)}$.

Then there are $N$ lines, each containing $M - 1$ positive integers, where the entry in row $i$ and column $j$ is $q_{(i,j)}$.

A single line follows with an integer $Q$, the number of queries.

Then $Q$ lines follow, each containing four integers $u$, $v$, $s$, $t$.

Output Format

Output $Q$ lines. For each query, print the expected time for $\text{Bob}$ to go from $(u, v)$ to $(s, t)$. You may output any number of decimal places, but your answer is considered correct only if the error rate is within $0.1\%$.

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

7.0000
10.0000
8.0000
10.0000

Hint

For $10\%$ of the testdata, $N \times M \le 25$.

For $30\%$ of the testdata, $N \times M \le 625$.

For $50\%$ of the testdata, $N \times M \le 2500$.

For $100\%$ of the testdata, $1 \le N \times M \le 10^4$, $1 \le Q \le 100$, and $1 \le p_{(i,j)}, q_{(i,j)} \le 200$.

Additionally, for $10\%$ of the testdata, $\min(N, M) \le 10$.

Translated by ChatGPT 5