问题 28491 --「ZJOI2016」旅行者

28491: 「ZJOI2016」旅行者

时间限制: 8 Sec  内存限制: 256 MB
提交: 1  解决: 1
[提交][状态][讨论版][数据上传:][下载FPS0元][下载测试数据0元][15560kb]

题目描述

小 Y 来到了一个新的城市旅行。她发现了这个城市的布局是网格状的,也就是有 nnn 条从东到西的道路和 mmm 条从南到北的道路,这些道路两两相交形成 n×mn \times mn×m 个路口 (i,j) (1≤i≤n,1≤j≤m)(i,j) \ (1 \leq i \leq n,1 \leq j \leq m)(i,j) (1in,1jm)

她发现不同的道路路况不同,所以通过不同的路口需要不同的时间。通过调查发现,从路口 (i,j)(i,j)(i,j) 到路口 (i,j+1)(i,j+1)(i,j+1) 需要时间 r(i,j)r(i,j)r(i,j),从路口 (i,j)(i,j)(i,j) 到路口 (i+1,j)(i+1 ,j)(i+1,j) 需要时间 c(i,j)c(i,j)c(i,j)。注意这里的道路是双向的。

小 Y 有 qqq 个询问,她想知道从路口 (x1,y1)(x_1,y_1)(x1,y1) 到路口 (x2,y2)(x_2,y_2)(x2,y2) 最少需要花多少时间。

输入

第一行包含两个正整数 n,mn,mn,m,表示城市的大小。
接下来 nnn 行,每行包含 m−1m-1m1 个整数,第 iii 行第 jjj 个正整数表示从一个路口到另一个路口的时间 r(i,j)r(i,j)r(i,j)
接下来 n−1n-1n1 行,每行包含 mmm 个整数,第 iii 行第 jjj 个正整数表示从一个路口到另一个路口的时间 c(i,j)c(i,j)c(i,j)
接下来一行,包含一个正整数 qqq,表示小 Y 的询问个数。
接下来 qqq 行,每行包含四个正整数 x1,y1,x2,y2x_1,y_1,x_2,y_2x1,y1,x2,y2,表示两个路口的位置。

输出

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

样例输入

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

样例输出

6
7

提示




对于所有的测试数据,n×m≤2×104, q≤105n \times m \leq 2 \times 10^4, \ q \leq 10^5 n×m2×104, q105,保证相邻路口之间的时间不超过 10410^4104,即 1r(i,j),c(i,j)104



来源

[提交][状态]