Translation for 2016 JOI Matryoshka

matryoshka.md

Translation credit to Kaz Nakao

You are ordering $N$ matryoshka dolls. They each have a diameter $R$ and a height $H$. A matryoshka doll will only fit inside another if the former's height and width are both strictly less than the latter's.

You also have $Q$ queries. Each of these $Q$ queries has two arguments: $A$ and $B$. For each of the queries, you need to answer the following question: Among the set of dolls that have minimum diameter $A$ and maximum height $B$, how can you fit these dolls in each other, making "towers" of dolls, so that the total number of "towers" is minimal?

Input

The first line will contain $N$ and $Q$. The next $N$ lines will contain $R_i$ and $H_i$ for each of the dolls. The next $Q$ lines will contain $A_j$ and $B_j$ for each of the queries.

Output

$Q$ lines, each containing the answer for the respective query.

Constraints

$1 <= N <= 200000$
$1 <= Q <= 200000$
$1 <= R_i, H_i <= 1000000000$ $(1 <= i <= N)$
$1 <= A_j, B_j <= 1000000000$ $(1 <= j <= Q)$

Example Input

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

Example Output

0
1
2

Example Output Explanation

For the first query, there are no dolls that have minimum diameter 10 and maximum height 5, so the answer is 0.

For the second query, only dolls number 1 and 7 query's requirements, and doll 7 fits in doll 2, so the answer is 1.

For the last query, dolls number 1, 2, 3, and 7 satisfy the requirements. Doll 7 fits in doll 1, and doll in fits in doll 3. Doll 2 does not fit in any of the other dolls. Thus, the answer for this query is 2.