[SDOI2014] 酗酒者

题目描述

$\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\%$ 内才算正确。

输入输出样例

输入样例 #1

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

输出样例 #1

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$。