#1416. 奶牛坐月子

奶牛坐月子

题目描述

一个106\red{10^6}106\red{10^6}列的网格图,上面有一些牛、花和一些矩形围栏,围栏在格子的边界上,牛和花在格子里,牛只能向下或向右走,牛也不能穿过围栏和地图边界,求每头牛它能到达的花的数量。

注意栅栏不会相交

img

输入格式

第一行一个数f\red f表示矩形围栏的数量。

接下来f行,每行四个数x1,y1,x2,y2\red{x_1,y_1,x_2,y_2},表示(x1,y1\red{x_1,y_1})在围栏内部矩形的左上角,(x2,y2\red{x_2,y_2})在右下角。

接下来一行一个数m表示花的数量。

接下来m行每行两个数x,y\red{x,y},表示在(x,y\red{x,y})处有一朵花。

接下来一行一个数n\red{n}表示牛的数量。

接下来n行每行两个数x,y\red{x,y},表示在(x,y\red{x,y})处有一头牛。

输出格式

总共n\red n行,每行一个数ans\red{ans},第i\red{i}个数表示第i\red i头牛能到ans\red{ans}个花。

样例

样例输入

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

样例输出

5
1
0
1
3
1
3
0

数据范围与提示

0<=f<=200000\red{0<=f<=200000}

0<=m<=200000\red{0<=m<=200000}

1<=n<=200000\red{1<=n<=200000}