题目描述

A near by pasture can be represented as a rectangular grid consisting of 106 rows and 106 columns. The rows are numbered with integers 1 through 106 top to bottom, the columns with integers 1 through 106 left to right.

A herd of n cows is scattered through the grid, each cow occupying a unit square. The pasture also contains m dandelion flowers (which cows like), again each occupying a unit square. Finally, the pasture contains p fences, each a rectangle running along the edges of unit squares. Fences do not intersect or touch. However, a fence may contain other fences inside the enclosed area.

Due to unfavorable wind conditions, cows can only move in two directions – down or right. Cows can go through squares occupied by other cows or flowers, but cannot cross fences. For each cow, find the total number of flowers reachable from its present location.

输入格式

Input contains three blocks – the first block describes fences, the second one flowers and the third one cows.

The first line of the first block contains an integer f (0≤ f ≤200000) – the number of fences. Each of the following f lines contains four integers r1, c1, r2, c2 (1≤r1, c1, r2, c2 ≤$10^6$) describing a single fence – r1 and c1 are the coordinates (row and column) of the upper-left corner square inside the fence, while r2 and c2 are the coordinates of the lower-right corner square inside the fence. No two fences will intersect or touch.

The first line of the second block contains an integer m (0≤m≤200000) – the number of flowers. The k-th of the following m lines contains two integers r and c (1 ≤ r, c ≤ $10^6$) – the location of the k-th flower. No two flowers will occupy the same location.

The first line of the third block contains an integer n (1≤n≤200000) – the number of cows. The k-th of the following n lines contains two integers r and c (1≤r, c≤$10^6$) – the location of the k-th cow. No two cows will occupy the same location, and no flower and cow will occupy the same location.

输出格式

Output should consist of n lines. The k-th line should contain a single integer – the total number of flowers reachable from the location of the k-th cow.

题目大意

题意简述

给定一个 $10^6$ 行 $10^6$ 列的网格图，上面有一些牛、花和一些不相交的矩形围栏。所有围栏在格子的边界上，同时牛和花在格子里。每头牛只能向下或向右走，同时不能穿过围栏和地图边界。

求每头牛能到达的花的数量。

输入格式

第一行一个数 $f$ 表示矩形围栏的数量。接下来 $f$ 行，每行四个数 $x_1,y_1,x_2,y_2$ ，表示 $(x_1,y_1)$ 在围栏内部矩形的左上角， $(x_2,y_2)$ 在右下角。

接下来一行一个数 $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 

提示

样例：

Central Europe Regional Contest 2015 Problem C