Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

data structures

divide and conquer

dp

*3000

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Julia the snail

time limit per test

2 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputAfter 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 *l*_{i} above the ground, and the higher end on the height *r*_{i} above the ground.

For some reason no two ropes share the same position of the higher end, i.e. all *r*_{i} 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

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 *l*_{i} and *r*_{i} (1 ≤ *l*_{i} ≤ *r*_{i} ≤ *n*) — the heights on which the lower and the higher ends of the *i*-th rope are fixed, respectively. It is guaranteed that all *r*_{i} 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

For each question print the maximum reachable for Julia height.

Examples

Input

8

4

1 2

3 4

2 5

6 7

5

1 2

1 4

1 6

2 7

6 8

Output

2

2

5

5

7

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

Output

2

7

3

3

2

2

5

3

7

10

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.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/22/2024 12:43:29 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|