文理学院程序设计在线练习


黑白图片

Time Limit: 2 Second(s)    Memory Limit: 32 MB

Total Submission(s): 37   Accepted Submission(s): 21
Problem Description

小明有一张黑白图片,长宽均为1000像素。他把图片的左下角放在笛卡尔直角坐标系的原点,图片的底边和x轴对齐。并按照图片的单位像素设置直角坐标的单位长度,这么一来,图片上的任意一点均可用一对非负整数坐标(x,y)来表示。而且由于是黑白图片,所以图片上的每个点(像素)均可用0或者1来表示,其中1代表黑色,0代表白色。

现在,好奇的小明开始向你提问:对于任意给定的一个矩形区域,里面到底包含了多少个黑点,当然边界上的点也算。其中,矩形区域用左下角和右上角的坐标给出。

Input

输入数据的第一行为一个正整数T(1<=T<=10), 表示测试数据的组数,然后是T组测试数据。
每组测试数据的第一行是一个整数n(n<=10000)代表该图片中的黑点的总数。
后面有n行数据,每行2个整数,中间用空格分隔,代表每个黑点的坐标x,y(0<=x,y<1000)。
接下来一个整数m(0<m<=2000),代表矩形区域的数量。
后面的m行,每行4个整数x1,y1,x2,y2,中间用空格分隔,代表每个矩形区域的左下角和右上角的坐标(0<=x1<=x2<1000,0<=y1<=y2<1000)。

Output

对于小明每个提问中的矩形区域,输出该矩形区域内黑点的总数。

Sample Input
2
5
1 7
2 4
3 0
8 8
9 4
2
0 0 5 5
1 4 9 8
3
0 0
1 1
3 3
2
0 0 2 2
4 0 7 2
Sample Output
2
4
2
0
Hint

输入数据较多,用scanf读入效率更高。
下图展示了2个sample测试的示例:


Author

flx

Source

usx第六届程序设计竞赛