| Tinkoff Challenge - Elimination Round |
|---|
| Закончено |
После тяжелой работы аналитику Игорю захотелось немного спокойствия.
Он решил завести себе улитку. Для этого он купил аквариум, в середине которого стоял крошечный гладкий ствол дерева и поместил в аквариум улитку, которую он назвал Юля.
Игорь заметил, что иногда Юля пытается подняться по стволу дерева, однако не может этого сделать, так как ствол гладкий. Чтобы помочь улитке, он подвесил на это дерево нитки, прицепив нижний конец i-й нитки на высоте li над землей, а верхний — на высоте ri.
Так получилось, что верхние концы всех ниток располагаются на разной высоте, то есть все ri различны. Теперь Юля может сползать по стволу вниз, а также подниматься вверх от нижнего конца некоторой веревки до верхнего. Игорь остался доволен своей работой, и теперь, когда он хочет отвлечься от работы, он задается вопросами о возможных перемещениях улитки. А именно, его интересуют вопросы следующего вида: «Предположим, сейчас Юля сидит на стволе на высоте x. Как высоко на стволе дерева она сможет оказаться, если никогда не будет опускаться ниже высоты x и никогда не будет подниматься выше высоты y?» Обратите внимание, Юля не может сползать с веревки на ствол до того, как доберется до верха веревки, и Игоря интересует конечное положение Юли на стволе дерева.
Игорь задается различными вопросами, и не всегда может самостоятельно на них ответить. Помогите Игорю, напишите программу, которая отвечает на соответствующие вопросы.
Первая строка содержит одно целое число 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 — высота, где Юля начнет свой путь (и ниже которой не может спускаться), и y — высота, выше которой она забираться не может.
Для каждого вопроса выведите одно целое число: максимальную высоту, на которую может подняться Юля.
8
4
1 2
3 4
2 5
6 7
5
1 2
1 4
1 6
2 7
6 8
2
2
5
5
7
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
7
3
3
2
2
5
3
7
10
Иллюстрация к первому примеру слева, иллюстрация ко второму примеру — справа. Различные цвета веревок ничего не значат и служат лишь для ясности изображений.
