引例3：区域和（二维前缀和）

题目描述

给定一个n×n的矩阵，有m次查询，每次查询一个子矩阵的元素和。

输入格式

第一行一个整数n，表示矩阵的大小。

接下来n行，每行n个整数，表示矩阵中的元素。

接下来一行一个整数m，表示查询次数。

接下来m行，每行四个整数x1, y1, x2, y2，表示查询从(x1,y1)到(x2,y2)的子矩阵的和。

输出格式

对于每个查询，输出一行一个整数，表示子矩阵的和。

输入输出样例

3
1 2 3
4 5 6
7 8 9
2
1 1 2 2
2 2 3 3

12
28