B. Fertilizer
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are a farmer. You own $$$F$$$ fields of land, which are arranged in a straight line. They are numbered $$$1 \ldots F$$$ from left to right.

You have recently acquired a crop duster, which is an airplane that can quickly spray fertilizer over a large amount of land. The crop duster is preprogrammed with $$$N$$$ possible trips, numbered $$$1 \ldots N$$$. In trip $$$i$$$, the crop duster flies over the fields $$$L_i \ldots R_i$$$, where $$$1 \leq L_i \leq R_i \leq F$$$, and sprays fertilizer over all these fields.

You now plan to use a consecutive set of preprogrammed trips. You would like to answer $$$Q$$$ questions, where the $$$j$$$-th question is the following:

  • If the crop duster makes trips $$$X_j \ldots Y_j$$$, where $$$1 \leq X_j \leq Y_j \leq N$$$, how many fields will be fertilized at least once?
Input

The first line contains a single integer $$$F$$$, the number of fields.

The second line contains a single integer $$$N$$$, the number of preprogrammed trips.

The next $$$N$$$ lines describe the trips. The $$$i$$$-th of these lines contains two integers $$$L_i$$$ and $$$R_i$$$.

The next line contains a single integer $$$Q$$$, the number of questions you wish to answer.

The next $$$Q$$$ lines describe the questions. The $$$j$$$-th of these lines contains two integers $$$X_j$$$ and $$$Y_j$$$.

Output

You should print $$$Q$$$ lines of output. The $$$j$$$-th line should consist of a single integer, the answer to the $$$j$$$-th question.

Scoring

The test data for this problem is divided into multiple subtasks. In order to pass a subtask, your submitted program must solve every test case within that subtask correctly and within the time and memory limits.

You will be awarded the points allocated to a subtask if at least one submission you make during the contest passes that subtask. You do not need to combine your solutions for multiple subtasks into a single submission.

Please keep in mind that the subtasks are not necessarily arranged in increasing order of difficulty. We encourage you to try as many subtasks as possible.

Constraints

In all test data, it is guaranteed that:

  • $$$1 \leq F \leq 10^6$$$.
  • $$$1 \leq N \leq 5 \cdot 10^5$$$.
  • $$$1 \leq L_i \leq R_i \leq F$$$, for all $$$1 \leq i \leq N$$$.
  • $$$1 \leq Q \leq 10^6$$$.
  • $$$1 \leq X_j \leq Y_j \leq N$$$, for all $$$1 \leq j \leq Q$$$.

Subtasks

  • Subtask 1 (4 points) $$$F, Q, N \leq 100$$$.
  • Subtask 2 (5 points) $$$F, Q, N \leq 2 \cdot 10^3$$$. Further, $$$X_j = 1$$$ for all $$$1 \le j \le Q$$$.
  • Subtask 3 (9 points) $$$F, Q, N \leq 2 \cdot 10^3$$$.
  • Subtask 4 (5 points) $$$N \leq 10^5$$$. Further, $$$R_i \lt L_{i+1}$$$ for all $$$1 \leq i \lt N$$$.
  • Subtask 5 (8 points) $$$N \leq 10^5$$$. Further, $$$L_i \lt L_{i+1}$$$ and $$$R_i \lt R_{i+1}$$$ for all $$$1 \leq i \lt N$$$.
  • Subtask 6 (10 points) $$$N, Q \leq 2 \cdot 10^4$$$.
  • Subtask 7 (8 points) $$$N, Q \leq 5 \cdot 10^4$$$. Further, $$$L_i = R_i$$$ for all $$$1 \leq i \leq N$$$.
  • Subtask 8 (15 points) $$$N \le 10^5$$$. Further, $$$X_j \le X_{j + 1}$$$ and $$$Y_j \le Y_{j + 1}$$$ for all $$$1 \le j \lt Q$$$.
  • Subtask 9 (15 points) $$$N \leq 10^5$$$.
  • Subtask 10 (21 points) No additional constraints
Examples
Input
5
3
1 4
2 3
4 5
4
1 2
2 3
1 3
1 1
Output
4
4
5
4
Input
10
4
1 4
2 5
7 8
8 10
4
1 4
1 2
4 4
3 4
Output
9
5
3
4
Input
10
5
4 8
2 2
1 3
5 7
9 10
5
1 1
1 2
1 3
1 4
1 5
Output
5
6
8
8
10
Input
10
5
1 4
2 10
3 6
5 8
2 6
5
1 2
3 4
3 5
4 5
5 5
Output
10
6
7
7
5
Input
10
7
1 4
2 3
4 7
5 10
3 5
6 8
1 2
5
1 7
2 5
3 4
6 7
1 3
Output
10
9
7
5
7
Note

In the first sample, there are $$$3$$$ trips : Trip $$$1$$$ being from field $$$1$$$ to $$$4$$$, trip $$$2$$$ being from field $$$2$$$ to $$$3$$$ and trip $$$3$$$ being from field $$$4$$$ to $$$5$$$.

In the first query, trips $$$1$$$ and $$$2$$$ are in consideration, and we can see fields $$$1$$$ and $$$4$$$ will be fertilized once, fields $$$2$$$ and $$$3$$$ twice, and field $$$5$$$ none. Thus, the answer is $$$4$$$.

Sample $$$1$$$ is valid for Subtasks $$$1$$$, $$$3$$$, $$$6$$$, $$$9$$$ and $$$10$$$.

Sample $$$2$$$ is valid for Subtasks $$$1$$$, $$$3$$$, $$$5$$$, $$$6$$$, $$$9$$$ and $$$10$$$.

Sample $$$3$$$ is valid for Subtasks $$$1$$$, $$$2$$$, $$$3$$$, $$$6$$$, $$$9$$$ and $$$10$$$.

Sample $$$4$$$ is valid for Subtasks $$$1$$$, $$$3$$$, $$$6$$$, $$$8$$$, $$$9$$$ and $$$10$$$.

Sample $$$5$$$ is valid for Subtasks $$$1$$$, $$$3$$$, $$$6$$$, $$$9$$$ and $$$10$$$.