Problem Description

There are $ N $ Takahashi-kun members in the AtCoder office.

AtCoder keeps a record of office entry and exit, and $ M $ entry and exit events have occurred since the recording started.

The $ i $ -th $(1\leq\ i\leq\ M)$ entry and exit record is represented by a pair of integers $(T\ _\ i, P\ _\ i)$, indicating that the $P\ _\ i$ -th Takahashi-kun entered the office if he was outside at time $T\ _\ i$, or exited the office if he was inside.

It is known that at the beginning of the recording, all Takahashi-kun members were outside the office, and currently, all are outside the office.

Answer the following $ Q $ queries:

In the $ i $ -th $(1\leq\ i\leq\ Q)$ query, a pair of integers $(A\ _\ i, B\ _\ i)$ is given, and you need to find the total duration during which both the $A\ _\ i$ -th and $B\ _\ i$ -th Takahashi-kun were inside the office during the recording period.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $T\ _\ 1$ $P\ _\ 1$ $T\ _\ 2$ $P\ _\ 2$ $\vdots$ $T\ _\ M$ $P\ _\ M$ $ Q $ $A\ _\ 1$ $B\ _\ 1$ $A\ _\ 2$ $B\ _\ 2$ $\vdots$ $A\ _\ Q$ $B\ _\ Q$

Output Format

Output $ Q $ lines. The $ i $ -th line $(1\leq\ i\leq\ Q)$ should contain the answer to the $ i $ -th query.

Sample Input and Output

Sample Input #1

3 8
10 1
20 2
30 1
40 3
60 3
70 1
80 2
90 1
3
1 2
1 3
2 3

Sample Output #1

20
0
20

Sample Input #2

10 20
10257 9
10490 4
19335 1
25893 5
32538 9
33433 3
38522 9
40629 9
42896 5
52106 1
53024 3
55610 5
56721 9
58286 9
63128 3
70513 3
70977 4
74936 5
79883 9
95116 9
7
1 3
3 9
1 9
4 9
1 5
5 9
3 5

Sample Output #2

18673
2107
15310
25720
17003
10317
16848

Notes/Hints

Constraints

• $2\leq\ N\leq2\times10\ ^\ 5$
• $2\leq\ M\leq2\times10\ ^\ 5$
• $1\leq\ T\ _\ 1\lt\ T\ _\ 2\lt\dotsb\lt\ T\ _\ M\leq10\ ^\ 9$
• $1\leq\ P\ _\ i\leq\ N\ (1\leq\ i\leq\ M)$
• For any $1\leq\ p\leq\ N$, there are an even number of $ i $ such that $P\ _\ i=p$
• $1\leq\ Q\leq2\times10\ ^\ 5$
• $1\leq\ A\ _\ i\lt\ B\ _\ i\leq\ N\ (1\leq\ i\leq\ Q)$
• All inputs are integers

Sample Explanation 1

The time periods during which the 3 Takahashi-kun members were inside the office are as shown in the following diagram:  The answers to each query are as follows:

• The time both the 1st and 2nd Takahashi-kun were inside the office simultaneously was twice, from time $ 20 $ to time $ 30 $ and from time $ 70 $ to time $ 80 $. Both durations are $ 10 $, so output their sum, which is $ 20 $.
• The 1st and 3rd Takahashi-kun were never inside the office simultaneously. Therefore, output $ 0 $.
• The time both the 2nd and 3rd Takahashi-kun were inside the office simultaneously was once, from time $ 40 $ to time $ 60 $. The duration is $ 20 $, so output $ 20 $.

见题面 Input 部分

见题面 Output 部分