Test1.B

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

给定一个m*m的方阵(m<=100),矩阵中每个数字x均满足0<=x<=1000。现在需要进行n(n<=10000)个询问,每个询问的格式如下:
给定x1,y1,x2,y2(x1<=x2, y1<=y2),求所有 列y满足y1<=y<=y2,行满足x1<=x<=x2 的元素的和。

Input

第一行为一个整数t,代表测试数据的组数。
以下每组测试数据第一行包含一个整数m。
然后后面m行是一个m*m的方阵。
然后给定询问次数n,接下来n行每行四个数字分别代表x1,y1,x2,y2。
方阵内所有元素的值均<=10000
 

Output

对每个询问,分别求出满足条件的元素的和,每个输出占一行。

Sample Input

1
2
1 1
1 1
2
1 1 1 1
1 1 2 2

Sample Output

1
4

Hint

 

Source

polla