← 返回题目列表

Codeforces · 793/F

F. 蜗牛朱莉娅

中文机器翻译题面 查看原题

辛苦工作后,伊戈尔决定休息一下。

他决定养一只蜗牛。他买了一个水族箱,中间有一根滑溜溜的树干,并在水族箱里放了一只名叫朱莉娅的蜗牛。

伊戈尔注意到,有时朱莉娅想爬上树干,但由于树干太滑而无法做到。为了帮助蜗牛,伊戈尔在树上放了一些绳子,将第 i 根绳子的下端固定在树干上距地面高度 li 的位置,将较高端固定在距地面高度 ri 的位置。

由于某种原因,没有两根绳子共享较高端的相同位置,即所有 ri 都是不同的。现在,朱莉娅可以在树干的任何位置向下移动,也可以从绳子的下端向上移动到其较高端。伊戈尔对他的工作感到自豪,有时会思考蜗牛可能的运动。也就是说,他对以下问题感兴趣:“假设蜗牛现在位于高度 x 的树干上。如果蜗牛的树干永远不会低于 x 或高于 y,那么它能爬到的最高位置是多少?»请注意,在到达绳子的较高端之前,Julia 无法从绳子移动到树干,而 Igor 对树干上的最高位置感兴趣。

伊戈尔对许多问题感兴趣,但并不总是能回答它们。帮助他,编写一个程序来回答这些问题。

输入

第一行包含单个整数 n (1 ≤ n ≤ 100000) — 树干的高度。

第二行包含单个整数 m (1 ≤ m ≤ 100000) — 绳索的数量。

接下来的 m 行包含有关绳索的信息。

这些行中的第 i 行包含两个整数 li 和 ri (1 ≤ li ≤ ri ≤ n) - 第 i 根绳子的下端和上端分别固定的高度。保证所有 ri 都是不同的。

下一行包含单个整数 q (1 ≤ q ≤ 100000) — 问题数。

接下来的 q 行包含有关问题的信息。

每行都包含两个整数 x 和 y (1 ≤ x ≤ y ≤ n),其中 x 是 Julia 开始的高度(以及 Julia 不能低于的高度),y 是 Julia 不能高于的高度。

输出

对于每个问题,打印 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

注意

左边是第一个样本的图片,右边是第二个样本的图片。绳索的颜色只是为了清晰起见,它们没有任何意义。