Matryoshka (Translated)

JOI Spring Training Camp 2015/16
Original Statement / Submission Site

Problem Statement

You plan to open a store selling Matryoshka dolls, so you have ordered N Matryoshka dolls from a factory. These dolls are numbered from 1 to N. The i-th doll (1 ≤ i ≤ N) can be regarded as a hollow circular cylinder with base diameter Ri cm and height Hi cm.

Matryoshka dolls can be stored by nesting one doll inside another. Each Matryoshka doll can store exactly one other doll that is strictly smaller in both base diameter and height. A stored doll may itself store another doll inside.

One day, the factory informs you that it cannot deliver all N dolls. Instead, only those dolls whose base diameter is at least A cm and height is at most B cm will be delivered to you.

The values of A and B may change suddenly. Therefore, for each of Q pairs (Aj, Bj) (1 ≤ j ≤ Q), you want to determine in advance the minimum number of Matryoshka dolls that will not be stored inside any other doll, no matter how you nest the delivered dolls.

Task

Given the dimensions of the N Matryoshka dolls and Q pairs (Aj, Bj), write a program that, for each pair, determines the minimum number of dolls that will not be stored inside any other doll, no matter how you nest the delivered dolls.

Input

• Line 1: Two integers N and Q – number of dolls and number of (A, B) queries.
• Next N lines: Each contains two integers Ri, Hi – base diameter and height of the i-th doll.
• Next Q lines: Each contains two integers Aj, Bj.

Output

Print Q lines. Each line contains the minimum number of dolls that are not nested inside any other doll for the corresponding (Aj, Bj) pair.

Constraints

• 1 ≤ N ≤ 200,000
• 1 ≤ Q ≤ 200,000
• 1 ≤ Ri, Hi, Aj, Bj ≤ 1,000,000,000

Subtasks

• Subtask 1 [11 points]: N ≤ 10, Q = 1
• Subtask 2 [15 points]: N ≤ 100, Q = 1
• Subtask 3 [25 points]: N ≤ 2,000, Q ≤ 2,000
• Subtask 4 [49 points]: No additional constraints

Sample Input 1

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

Sample Output 1

0
1
2

Explanation of Output 1

• (A, B) = (10, 5): No dolls are delivered, so the output is 0.
• (A, B) = (3, 5): Dolls 1 and 7 are delivered. You can nest doll 7 into doll 1, so the output is 1.
• (A, B) = (3, 9): Dolls 1, 2, 3, 7 are delivered. You can nest doll 7 → doll 1 → doll 3, so the output is 2.

Sample Input 2

10 8
14 19
9 16
11 2
7 18
20 16
9 5
10 9
20 6
4 17
13 8
7 14
9 3
9 13
4 19
12 4
19 16
18 10
7 14

Sample Output 2

3
1
3
5
0
2
1
3