LightYoungWoo

Time limit1sMemory limit512 MB

Summary

Given N lights that each illuminate a 90-degree upward sector, count for each query point how many sectors contain it.

Level: Medium5 of 10
Topics: Geometry, Prefix sum, Binary search, Sorting
Solved: No attempts yet

Problem

Let north be the $+y$ direction. There are $N$ lights in the plane, with the $i$ -th light at $(X_i, Y_i)$ .

Each light illuminates a $90$ -degree sector centered on north. A point $(X, Y)$ receives light from the $i$ -th light exactly when

$Y \ge Y_i \quad \text{and} \quad |X - X_i| \le Y - Y_i$

The boundary is included, so the point where a light stands is illuminated by that light. When several lights cover the same point, their intensities add up. That is, the intensity at $(X, Y)$ equals the number of lights satisfying the condition above.

Input

The input is given from standard input. The first line contains the number of lights $N$ ( $1 \le N \le 100000$ ).

The next $N$ lines each contain two integers $X_i, Y_i$ ( $-1500 \le X_i, Y_i \le 1500$ ), the position of each light.

The next line contains the number of query points $P$ ( $1 \le P \le 100000$ ).

The next $P$ lines each contain two integers $X_{pi}, Y_{pi}$ ( $-1500 \le X_{pi}, Y_{pi} \le 1500$ ), the coordinates of each point whose intensity is asked.

Output

Print $P$ lines to standard output. The $i$ -th line contains the light intensity at $(X_{pi}, Y_{pi})$ .

Examples1

Example 1
Input
```
2
3 1
6 0
3
1 3
4 5
8 4
```
Expected output
```
1
2
1
```