Intersection Construction

Interview

Time limit2sMemory limit1024 MB

Summary

Given N intervals and Q queries [l, r], find the fewest intervals whose intersection is exactly [l, r], or print -1 if no selection works.

Level: Medium4 of 10
Topics: Array, Hash map, Implementation
Solved: No attempts yet

Problem

An interval $[l,r]$ is the set of all real numbers that are at least $l$ and at most $r$ .

$N$ intervals are given. Write a program that answers $Q$ queries of the following form.

For the given $l$ and $r$ , can you choose one or more of the intervals so that their intersection is exactly $[l,r]$ ? If so, what is the minimum number of intervals you must choose?

Input

The first line contains the number of intervals $N$ . ( $1 \leq N \leq 300000$ )

Each of the next $N$ lines contains two integers $l_i$ and $r_i$ , separated by a space, which describe the interval $[l_i,r_i]$ . ( $0 \leq l_i < r_i \leq 10^6$ )

The next line contains the number of queries $Q$ . ( $1 \leq Q \leq 300000$ )

Each of the next $Q$ lines contains two integers $l$ and $r$ , separated by a space. ( $0 \leq l < r \leq 10^6$ )

Output

For each query, print one line. If no selection of intervals has intersection exactly $[l,r]$ , print $-1$ . Otherwise, print the minimum number of intervals that must be selected.

Examples1

Example 1
Input
```
3
0 10
2 6
4 8
3
4 6
2 8
1 9
```
Expected output
```
2
-1
-1
```