题目描述
小 Y 来到了一个新的城市旅行。她发现了这个城市的布局是网格状的,也就是有 n 条从东到西的道路和 m 条从南到北的道路,这些道路两两相交形成 n×m 个路口 (i,j), (1≤i≤n,1≤j≤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 行,每行包含一个整数表示从一个路口到另一个路口最少需要花的时间。
提示
数据规模与约定
- n×m≤2×104。
- q≤105。
- 1≤r(i,j),c(i,j)≤104。