#4422. [Cerc2015]Cow Confinement

题目描述

一个10^6行10^6列的网格图，上面有一些牛、花和一些矩形围栏，围栏在格子的边界上，牛和花在格子里，牛只能向下或向右走，牛也不能穿过围栏和地图边界，求每头牛它能到达的花的数量。注意栅栏不会相交

输入格式

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

接下来f行，每行四个数x1,y1,x2,y2，表示(x1,y1)在围栏内部矩形的左上角，(x2,y2)在右下角。

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

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

接下来一行一个数n表示牛的数量。

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

输出格式

总共n行，每行一个数ans，第i个数表示第i头牛能到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

0<=m<=200000

1<=n<=200000