Bob gave Alice a set of rectangles. Each rectangle has a length and a height.
Alice introduced the concept of nesting, that is, in rectangle \(A\), you can put a rectangle \(B\) when both the following conditions are met:
- The length of rectangle \(A\) is greater than the length of rectangle \(B\).
- The height of rectangle \(A\) is greater than the length of rectangle \(B\).
Only one rectangle can be embedded in one rectangle but it can be as follows:
Let \(A\) be embedded in \(B\) and \(B\) be embedded in \(C\), then \(A\) can be embedded in \(B\) first, and then \(B\) can be embedded in \(C\).
Alice came up with the following problem, which is that she wants to know several times for certain \(c\) and \(d\) the minimum number of rectangles that can remain after nesting in each other among all those rectangles in which the length is not less than \(c\) and the height is not more than \(d\).
Input format
- The first line contains two numbers \(n\) and \(m\) denoting the number of rectangles and the number of queries, respectively.
- In each of the next \(n\) lines, there are two numbers \(A_i\) and \(B_i\) denoting the length and height of the \(i\)-th rectangle.
- In each of the next \(m\) lines, there are two numbers \(c_j\) and \(d_j\) denoting query parameters.
Output format
Print \(m\) lines, one line in each line, denoting the answer to the problem for \(j\) query.
Constraints
\(1 ⩽ n, m ⩽ 2 * 10^5\)
\(1 ⩽ A_i, B_i ⩽ 10^9\)
\(1 ⩽ c_j, d_j ⩽ 10^9\)
(c, d) = (10,5) - since there is no rectangle in which length not less than 10 and height not more than 5, the answer is 0.
(c, d) = (3,5) - exists only two rectangles (rectangle numbers 1 and 7 (9.5) and (4.1)). Since the rectangle is numbered 7 can be enclosed in a rectangle numbered 1, then answer 1.
(c, d) = (3,9) - rectangles under numbers 1, 2, 3 and 7. In this case a rectangle with number 7 can be nested in a rectangle with number 1, and a rectangle with number 1 can be enclosed in a rectangle numbered 3. Therefore, answer 2.
