달팽이 Julia

열심히 일한 뒤 Igor는 좀 쉬기로 했다.

그는 달팽이를 기르기로 했다. 가운데에 미끄러운 나무줄기가 있는 수조를 사서 Julia라는 달팽이를 수조에 넣었다.

Igor는 Julia가 가끔 나무줄기를 기어오르고 싶어 하지만, 나무줄기가 너무 미끄러워 그러지 못한다는 것을 알아차렸다. 달팽이를 돕기 위해 Igor는 나무에 밧줄 몇 개를 설치하여, i-th 밧줄의 아래쪽 끝을 지면에서 li 높이의 나무줄기에 고정하고 위쪽 끝을 지면에서 ri 높이에 고정했다.

어떤 이유에서인지 위쪽 끝의 위치가 같은 두 밧줄은 없다. 즉, 모든 ri는 서로 다르다. Now Julia는 나무줄기의 어느 위치에서든 아래로 이동할 수 있으며, 어떤 밧줄의 아래쪽 끝에서 그 밧줄의 위쪽 끝까지 올라갈 수도 있다. Igor는 자신이 한 일을 자랑스럽게 여기며, 가끔 달팽이가 이동할 수 있는 방법에 관해 생각한다. 구체적으로 그는 다음 질문들에 관심이 있다. «현재 달팽이가 나무줄기의 높이 x에 있다고 하자. 달팽이가 x보다 낮아지거나 y보다 높아지는 일이 전혀 없다면, 나무줄기에서 도달할 수 있는 가장 높은 위치는 어디인가?» Julia는 밧줄의 위쪽 끝에 도달하기 전에는 밧줄에서 나무줄기로 이동할 수 없으며, Igor가 관심 있는 것은 나무줄기에서의 가장 높은 위치임에 유의한다.

Igor는 많은 질문에 관심이 있지만 항상 그 답을 구할 수 있는 것은 아니다. 그를 도와 이 질문들에 답하는 프로그램을 작성한다.

첫째 줄에 나무줄기의 높이를 나타내는 하나의 정수 n (1 ≤ n ≤ 100000)가 주어진다.

둘째 줄에 밧줄의 수를 나타내는 하나의 정수 m (1 ≤ m ≤ 100000)가 주어진다.

다음 m개의 줄에 밧줄에 관한 정보가 주어진다.

이 줄들 중 i-th번째 줄에는 두 정수 li와 ri (1 ≤ li ≤ ri ≤ n)가 주어지며, 각각 i-th 밧줄의 아래쪽 끝과 위쪽 끝이 고정된 높이를 나타낸다. 모든 ri가 서로 다름이 보장된다.

다음 줄에 질문의 수를 나타내는 하나의 정수 q (1 ≤ q ≤ 100000)가 주어진다.

다음 q개의 줄에 질문에 관한 정보가 주어진다.

각 줄에는 두 정수 x와 y (1 ≤ x ≤ y ≤ n)가 주어진다. 여기서 x는 Julia가 출발하는 높이이자 Julia가 그보다 낮아질 수 없는 높이이고, y는 Julia가 그보다 높아질 수 없는 높이이다.

각 질문에 대해 Julia가 도달할 수 있는 최대 높이를 출력한다.

첫 번째 예제의 그림은 왼쪽에 있고, 두 번째 예제의 그림은 오른쪽에 있다. 밧줄의 색은 알아보기 쉽게 하기 위한 것일 뿐, 아무 의미도 없다.