题目描述

Alice 发现：人在心情不好的时候，便会选择酗酒。这往往与 OI 选手比赛胜利后的欢腾庆祝不同，酗酒者喝醉后便会忘记回家的路，然后在大街上无规律地乱走乱逛，同时喊着一些谁也听不懂的话。

这几天， Bob 因为考试的原因心情很不好，每天晚上都会在城里面找一处酒吧。喝醉后离开酒吧开始在城市街道中无规律乱走，直到某一时刻，若他碰巧遇到了在夜晚出来看星星的 Alice ，便会被她带回家。

已知 Alice 和 Bob 所在的城市街道可以被描绘为一个 $n$ 行 $m$ 列的格点地图，$n$ 行依次编号为 $0$ 到 $n-1$，$m$ 列依次编号为 $0$ 到 $m-1$。城市中共有 $n×m$ 处路口，每一个路口可以用坐标 $(i,j)$ 表示。若 $i$ 对于给定的两个点 $(u,v)$ 和 $(s,t)$ 分别为 Bob 今晚去的酒吧的位置，和 Alice 今晚看星星的位置。 Bob 离开酒吧后，对于每一个路口，他会等概率选择其中之一，然后走向下一个路口。

在走到下一个路口之前， Bob 不会回头。同时 Bob 并不会因为之前走过什么道路而影响之后的行走路线。

具体来说：如果 Bob 从 $(3,4)$ 走到 $(3,5)$，他有可能在抵达 $(3,5)$ 后立刻折回 $(3,4)$。对于四叉路口， Bob 向每一个方向行走的概率都是 $\frac14$，对于三叉路口（这只存在于城市的边界上）则是 $\frac13$，对于二叉路口（这只存在于城市的 $4$ 个角落）就是 $\frac12$。

Alice 希望知道，从 Bob 离开酒吧， Alice 期望情况下还需要等多久才能等到 Bob ，即对于给定的两个点 $(u,v)$ 与 $(s,t)$， Bob 从 $(u,v)$ 走到 $(s,t)$ 的期望用时是多少？

输入格式

第一行 $n,m$。之后 $n-1$ 行，每行 $m$ 个正整数，其中第 $i$ 行第 $j$ 个为 $p[i][j]$。

之后 $n$ 行，每行 $m-1$ 个正整数，其中第 $i$ 行第 $j$ 个为 $q[i][j]$。

单独一行给出一个整数 $Q$，表示总询问次数。

之后 $Q$ 行，每行有四个整数 $u,v,s,t$。

输出格式

一共 $Q$ 行，每一行对应一次询问：从 $(u,v)$ 走到 $(s,t)$ 的期望距离是多少？你的答案可以保留任意多位小数，但只有与正确答案的错误率在 $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

数据范围与提示

对于 $10\%$ 的数据，$n\times m\le 25$。

对于 $30\%$ 的数据，$n\times m\le 625$。

对于 $50\%$ 的数据，$n\times m\le 2.5\times 10^3$。

对于 $100\%$ 的数据，$n\times m\le 10^4$，$Q\le 100$，$p[i][j],q[i][j]\le 200$ （$1\le i\le n$，$1\le j\le m$）。

此外，存在 $10\%$ 的数据，$min(n,m)\le 10$。