Younger Sibling of a Right Triangle

Interview

Time limit3sMemory limit1024 MB

Summary

For each query (a, b), count the black points inside or on the boundary of the triangle with vertices (0, 0), (a, b), and (a, 0).

Level: Medium6 of 10
Topics: Geometry, Sorting, Prefix sum
Solved: No attempts yet

Problem

A voice actor deeply moved by the post "The younger sibling of a right triangle is also a right triangle!" decided to write a problem about right triangles. The problem is as follows.

There are $N$ black points on a two-dimensional plane. The $x$ and $y$ coordinates of all these points are positive. You must answer $M$ queries.

For each query point $(a\_i, b\_i)$ , count the black points inside the triangle whose vertices are $(0, 0)$ , $(a\_i, b\_i)$ , and $(a\_i, 0)$ . Points on the boundary of the triangle count as inside the triangle.

The voice actor found it too tedious to work out a solution and fell asleep. Solve the problem for them!

Input

The first line contains the number of points $N$ . $(1 \leq N \leq 100\, 000)$

The next $N$ lines each contain two integers $x\_i$ and $y\_i$ , separated by a space, the coordinates of a black point. All black points have distinct coordinates. $(1 \leq x\_i, y\_i \leq 10^9)$

The next line contains the number of queries $M$ . $(1 \leq M \leq 100\, 000)$

The next $M$ lines each contain two integers $a\_i$ and $b\_i$ , separated by a space. $(1 \leq a\_i, b\_i \leq 10^9)$

Output

Print $M$ lines. On the $i$ -th line, print the answer to the $i$ -th query.

Examples1

Example 1
Input
```
3
1 1
1 2
2 1
3
1 1
2 4
3 3
```
Expected output
```
1
3
2
```