题目描述

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

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

已知 $\text{Alice}$ 和 $\text{Bob}$ 所在的城市街道可以被描绘为一个 $N$ 行 $M$ 列的格点地图， $N$ 行依次编号为 $0$ 到 $N-1$ ， $M$ 列依次编号为 $0$ 到 $M-1$ 。城市中共有 $N \times M$ 处路口，每一个路口可以用坐标 $(i,j)$ 表示。若 $i<N$ ，则 $(i,j)$ 与 $(i+1,j)$ 有无向的连边，边权长度 ， $p_{(i,j)}$ 表示走过这一条路所需的时间。若 $j<M$ ，则 $(i,j)$ 与 $(i,j+1)$ 有连无向边，边权长度 $q_{(i,j)}$ 。

对于给定的两个点 $(u,v)$ 和 $(s,t)$ 分别为 $\text{Bob}$ 今晚去的酒吧的位置，和 $\text{Alice}$ 今晚看星星的位置。 $\text{Bob}$ 离开酒吧后，对于每一个路口，他会等概率选择其中之一，然后走向下一个路口。在走到下一个路口之前， $\text{Bob}$ 不会回头。同时 $\text{Bob}$ 并不会因为之前走过什么道路而影响之后的行走路线。

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

$\text{Alice}$ 希望知道，从 $\text{Bob}$ 离开酒吧， $\text{Alice}$ 期望情况下还需要等多久才能等到 $\text{Bob}$ ，即对于给定的两个点 $(u,v)$ 与 $(s,t)$，$\text{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$ 行，每行有 $4$ 个整数 $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 2500$。

对于 $100\%$ 的数据， $1\leq N \times M \le 10^4$ ， $1\leq Q\leq 100$ 。 $\forall i,j$ , $1\leq p_{(i,j)},q_{(i,j)} \le 200$，$N,M\geq 1$。

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