Problem Description

$ N $ pirates, numbered from $ 1 $ to $ N $, are dividing $ 10^{12} $ treasures, numbered from $ 1 $ to $ 10^{12} $. Each pirate has preferences for the treasures they want, where pirate $ i $ only wants treasures with numbers between $ L_i $ and $ R_i $ inclusive. There is an unwritten rule among the pirates that "a pirate with a higher number should receive the leftovers from pirates with lower numbers," so for all $i,j\ (1\ \leq\ i\ \lt\ j\ \leq\ N)$, it holds that $L_j\ \leq\ L_i$ and $R_i\ \leq\ R_j$.

The pirates have been pondering various ways to divide the treasures. Process the following $ Q $ queries in order:

• When dividing treasures among pirates $l, l+1, \ldots, r$, what is the maximum possible minimum number of treasures each pirate can receive?

Input Format

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

$ N $ $ L_1 $ $ R_1 $ $ L_2 $ $ R_2 $ $\hspace{0.5cm}\vdots$ $ L_N $ $ R_N $ $ Q $ $\text{query}_1$ $\text{query}_2$ $\hspace{0.4cm}\vdots$ $\text{query}_Q$

The content of the $ i $th query is represented by $\text{query}_i$ and is given in the following format:

$ l $ $ r $

Output Format

Output $ Q $ lines. The $ i $th line should contain the answer to the $ i $th query.

Sample Input and Output

Sample Input #1

2
2 4
1 5
2
1 2
2 2

Sample Output #1

2
5

Sample Input #2

10
545730128881 685343573126
495640031759 777974687460
441446188770 793309056685
376909511228 836745593749
371724504348 838698721858
232388555737 839645478663
171431376831 859733468976
64650919635 891249391583
54537347654 900209259449
7975806821 908972571709
10
9 9
2 3
1 6
3 9
2 10
1 2
3 4
5 6
2 9
7 8

Sample Output #2

845671911796
175931433958
93394843502
120810273113
100110751654
139613444246
229918041261
303628461463
105708988974
413299235974

Notes/Hints

Constraints

• $2\ \leq\ N\ \leq\ 10^5$
• $1\ \leq\ Q\ \leq\ 2\ \times\ 10^5$
• $1\ \leq\ L_i\ \leq\ R_i\ \leq\ 10^{12}\ (1\ \leq\ i\ \leq\ N)$
• For all $i,j\ (1\ \leq\ i\ \lt\ j\ \leq\ N)$, $L_j\ \leq\ L_i$ and $R_i\ \leq\ R_j$ are satisfied
• For each query, $1\ \leq\ l\ \leq\ r\ \leq\ N$ is satisfied
• All inputs are integers

Extra Cases

Correctly solving the dataset satisfying the below constraints (which includes $ 800 $ test cases satisfying the above constraints) will award an additional $ 1 $ point. However, it is not guaranteed that an AC solution with a slow language is possible for this dataset.

• $2\ \leq\ N\ \leq\ 5\ \times\ 10^5$
• $1\ \leq\ Q\ \leq\ 5\ \times\ 10^5$

Sample Explanation 1

For the first query, one possible way to divide the treasures is as follows:
- Assign treasures $ 2, 3 $ to pirate $ 1 $ and treasures $ 4, 5 $ to pirate $ 2 $.
For the second query, assigning all treasures $ 1, 2, 3, 4, 5 $ to pirate $ 2 $ is sufficient.

Sample Explanation 2

Original idea: penguinman

见题面 Input 部分

见题面 Output 部分