[ZJOI2016] 旅行者

题目描述

小 Y 来到了一个新的城市旅行。她发现了这个城市的布局是网格状的,也就是有 $n$ 条从东到西的道路和 $m$ 条从南到北的道路,这些道路两两相交形成 $n\times m$ 个路口 $(i,j)$, $(1\leq i\leq n,1\leq j\leq m)$ 她发现不同的道路路况不同,所以通过不同的路口需要不同的时间。通过调查发现,从路口 $(i,j)$ 到路口 $(i,j+1)$ 需要时间 $r(i,j)$ ,从路口 $(i,j)$ 到路口 $(i+1,j)$ 需要时间 $c(i,j)$ 。注意这里的道路是双向的。小 Y 有 $q$ 个询问,她想知道从路口 $(x1,y1)$ 到路口 $(x2,y2)$ 最少需要花多少时间。

输入输出格式

输入格式


第一行包含 2 个正整数 $n,m$ 表示城市的大小。 接下来 $n$ 行,每行包含 $m-1$ 个整数,第 $i$ 行第 $j$ 个正整数表示从一个路口到另一个路口的时间 $r(i,j)$ 。 接下来 $n-1$ 行,每行包含 $m$ 个整数,第 $i$ 行第 $j$ 个正整数表示从一个路口到另一个路口的时间 $c(i,j)$。 接下来一行,包含一个正整数 $q$,表示小 Y 的询问个数。 接下来 $q$ 行,每行包含 $4$ 个正整数 $x1,y1,x2,y2$,表示两个路口的位置。

输出格式


输出共 $q$ 行,每行包含一个整数表示从一个路口到另一个路口最少需要花的时间。

输入输出样例

输入样例 #1

2 2
2
3
6 4
2
1 1 2 2
1 2 2 1

输出样例 #1

6
7

说明

### 数据规模与约定 - $n\times m \le 2\times 10^4$。 - $q \le 10^5$。 - $1 \le r(i,j),c(i,j) \le 10^4$。