An interval $[l, r]$ is defined as the set of all real numbers $x$ such that $l \le x \le r$.

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

• Given $l$ and $r$, is it possible to select one or more of the given intervals such that their intersection is exactly $[l, r]$? If it is possible, what is the minimum number of intervals that must be selected?

Input

The first line contains the number of intervals $N$ ($1 \le N \le 300\,000$).

The next $N$ lines each contain two space-separated integers $l_i$ and $r_i$, representing the interval $[l_i, r_i]$ ($0 \le l_i < r_i \le 10^6$).

The next line contains the number of queries $Q$ ($1 \le Q \le 300\,000$).

The next $Q$ lines each contain two space-separated integers $l$ and $r$, representing the query interval $[l, r]$ ($0 \le l < r \le 10^6$).

Output

For each query, output the minimum number of intervals required to make their intersection exactly $[l, r]$. If it is impossible, output $-1$.

Examples

Input 1

3
0 10
2 6
4 8
3
4 6
2 8
1 9

Output 1

2
-1
-1