Julia the snail
Contest: Tinkoff Challenge - Elimination Round
Difficulty rating: 3000
Tags: data structures, divide and conquer, dp

After hard work Igor decided to have some rest.

He decided to have a snail. He bought an aquarium with a slippery tree trunk in the center, and put a snail named Julia into the aquarium.

Igor noticed that sometimes Julia wants to climb onto the trunk, but can't do it because the trunk is too slippery. To help the snail Igor put some ropes on the tree, fixing the lower end of the i-th rope on the trunk on the height li above the ground, and the higher end on the height ri above the ground.

For some reason no two ropes share the same position of the higher end, i.e. all ri are distinct. Now Julia can move down at any place of the trunk, and also move up from the lower end of some rope to its higher end. Igor is proud of his work, and sometimes think about possible movements of the snail. Namely, he is interested in the following questions: «Suppose the snail is on the trunk at height x now. What is the highest position on the trunk the snail can get on if it would never be lower than x or higher than y?» Please note that Julia can't move from a rope to the trunk before it reaches the higher end of the rope, and Igor is interested in the highest position on the tree trunk.

Igor is interested in many questions, and not always can answer them. Help him, write a program that answers these questions.

Input format:
The first line contains single integer n (1  ≤  n ≤  100000) — the height of the trunk.

The second line contains single integer m (1  ≤  m  ≤  100000) — the number of ropes.

The next m lines contain information about the ropes.

The i-th of these lines contains two integers li and ri (1  ≤ li ≤ ri ≤ n) — the heights on which the lower and the higher ends of the i-th rope are fixed, respectively. It is guaranteed that all ri are distinct.

The next line contains single integer q (1  ≤  q  ≤  100000) — the number of questions.

The next q lines contain information about the questions.

Each of these lines contain two integers x and y (1  ≤ x ≤ y ≤ n), where x is the height where Julia starts (and the height Julia can't get lower than), and y is the height Julia can't get higher than.

Output format:
For each question print the maximum reachable for Julia height.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
The picture of the first sample is on the left, the picture of the second sample is on the right. Ropes' colors are just for clarity, they don't mean anything.

Example input:
8
4
1 2
3 4
2 5
6 7
5
1 2
1 4
1 6
2 7
6 8

Example output:
2
2
5
5
7

Example input:
10
10
3 7
1 4
1 6
5 5
1 1
3 9
7 8
1 2
3 3
7 10
10
2 4
1 7
3 4
3 5
2 8
2 5
5 5
3 5
7 7
3 10

Example output:
2
7
3
3
2
2
5
3
7
10

Editorial:
At first, let's solve this task with O(r - l) time complexity for each query.
For each i, let's store backi if there is exists a segment [backi; i] (there's at most one such segment for every i).
For query [l, r], let's go from l to r, storing rightmost x, that is reachable from l (at start it is l), then if (l ≤ backi ≤ x), then we can add segment [backi, i] to answer, and say that x = i.
Now let's apply the following idea. If we found answer for some p (l ≤ p ≤ r) answer for query [l, p], we can find can find answer in O(r - p) time complexity for the whole query [l, r].
Let's find answers for all p that are divisable by k (for some k).
For this we have to to calculate additional array go[i][j] that stores answer for segment [i, j * k].
For this we need to calculate additional array to[i][j] - maximal right border, with left border equal to i, that  ≤  k * j (we can calc this with two pointers method).
To find array go, run from right to left, and for each j find answer:
go[i][j] = max(go[k][j]), (i ≤ k ≤ to[i][j])
Now we can notice that because we go from right to left that if element should be relaxed with some element i, it will be relaxed also with all elements p, so to[p][j] ≥ i. We can store stack for each j, pop from them all elements so their index  ≤ to[i][j], relax with them current value, and then add to stack current value with current index.
So we have found array go.
Then for answering query, if r - l ≤ k solve naive in O(r - l) else let p be the closest to r number that divides k. $$x \rightarrow go[i][\frac{r}{k}]$$, then for O(r - x) solve other query part.
Now time complexity is: $${\mathcal O}\left(q*k+n*\frac{n}{k}\right)$$
Optimal choice of k is $$k \approx \sqrt{n}$$.