蜗牛 Julia

• 时间限制：2 秒
• 内存限制：512 MiB

题目描述

水族箱中央有一根高度为 $n$ 的竖直树干。树干很滑，蜗牛 Julia 可以在树干上任意向下移动，却不能直接沿树干向上爬。

Igor 在树干上安装了 $m$ 根绳索。第 $i$ 根绳索的下端固定在高度 $l_i$，上端固定在高度 $r_i$。Julia 到达某根绳索的下端后，可以沿绳索爬到它的上端；一旦开始攀爬，必须到达绳索上端后才能回到树干。所有绳索上端的高度 $r_i$ 两两不同。

有 $q$ 次互相独立的询问。一次询问给出 $x,y$：Julia 从高度 $x$ 出发，整个移动过程中不得低于 $x$，也不得高于 $y$。求她能够到达的最高高度。

输入格式

第一行一个整数 $n$，表示树干高度。

第二行一个整数 $m$，表示绳索数量。

接下来 $m$ 行，每行两个整数 $l_i,r_i$，描述一根绳索。保证所有 $r_i$ 两两不同。

下一行一个整数 $q$，表示询问数量。

接下来 $q$ 行，每行两个整数 $x,y$，描述一次询问。

输出格式

对每次询问输出一行一个整数，表示 Julia 能够到达的最高高度。

样例输入 1

8
4
1 2
3 4
2 5
6 7
5
1 2
1 4
1 6
2 7
6 8

样例输出 1

2
2
5
5
7

样例输入 2

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

样例输出 2

2
7
3
3
2
2
5
3
7
10

数据范围

$1\le n,m,q\le 100000$，$1\le l_i\le r_i\le n$，$1\le x\le y\le n$。