Problem Description

A passport is a certificate used by travelers when entering foreign countries.

On a planet, there are $N$ countries numbered from $1$ to $N$. Each country issues a specific type of passport. When a traveler obtains a passport issued by country $i \ (1 \le i \le N)$, they can enter countries $L_i, L_{i+1}, \ldots, R_i$. It is guaranteed that the traveler can enter the country that issued the passport. Formally, $L_i \le i \le R_i$ holds.

You have a friend who loves to travel. Although he dreams of traveling around the world, he initially has no passports. Therefore, he plans to visit all $N$ countries by repeatedly performing the following two actions:
- Obtain a passport issued by the country he is currently in.
- Use one of his existing passports to enter another country.

Upon hearing his plan, you wonder if it is feasible and, if so, the minimum number of passports he needs. Since you do not know which country he is currently in, you consider $Q$ possible countries $X_1, X_2, \ldots, X_Q$ where he might be.

Given the passport information for each country ($L_i, R_i$) and the list of possible countries he might be in, you need to write a program that, for each possible country, determines whether he can visit all $N$ countries and, if possible, calculates the minimum number of passports required.

Input Format

Read from standard input:

$N$

$L_1 \ R_1$

$L_2 \ R_2$

$\vdots$

$L_N \ R_N$

$Q$

$X_1$

$X_2$

$\vdots$

$X_Q$

Output Format

Output $Q$ lines to standard output. The $j$-th line $(1 \le j \le Q)$ should contain the minimum number of passports required if your friend is in country $X_j$, or $-1$ if it is impossible for him to visit all $N$ countries.

Sample Input and Output

Sample Input #1

4
1 3
2 4
2 3
4 4
1
1

Sample Output #1

2

Sample Input #2

5
1 5
2 4
2 3
3 5
1 5
1
3

Sample Output #2

4

Sample Input #3

5
1 1
2 3
1 5
3 4
5 5
5
1
2
3
4
5

Sample Output #3

-1
2
1
2
-1

Sample Input #4

4
1 2
1 2
3 4
3 4
4
1
2
3
4

Sample Output #4

-1
-1
-1
-1

Notes/Hints

Sample Explanation #1

If your friend lives in country $X_1 = 1$, he can visit all $4$ countries by following these steps, obtaining $2$ passports:
1. Obtain a passport from country $1$.
2. Use the passport from country $1$ to travel to country $2$.
3. Obtain a passport from country $2$.
4. Use the passport from country $1$ to travel to country $3$.
5. Use the passport from country $2$ to travel to country $4$.

It is impossible to achieve this with fewer than $2$ passports, so the output is $2$.

Sample Explanation #2

If your friend lives in country $X_1 = 3$, he can visit all $5$ countries by following these steps, obtaining $4$ passports:
1. Obtain a passport from country $3$.
2. Use the passport from country $3$ to travel to country $2$.
3. Obtain a passport from country $2$.
4. Use the passport from country $2$ to travel to country $4$.
5. Obtain a passport from country $4$.
6. Use the passport from country $4$ to travel to country $5$.
7. Obtain a passport from country $5$.
8. Use the passport from country $5$ to travel to country $1$.

It is impossible to achieve this with fewer than $4$ passports, so the output is $4$.

Sample Explanation #3

For example, if your friend lives in country $X_3 = 3$, he can achieve his goal by obtaining a passport from country $3$ and using it to visit countries $1, 2, 4, 5$ in order. Thus, the third line outputs $1$.

However, if your friend lives in country $X_5 = 5$, he cannot enter any other country even if he obtains a passport from country $5$. Therefore, he cannot fulfill his travel plan, and the fifth line outputs $-1$.

Sample Explanation #4

This sample satisfies the constraints of subtasks $4 \sim 5$.

Data Range

For all test cases, the following constraints apply:
- $2 \le N \le 2 \times 10^5$
- $1 \le L_i \le i \le R_i \le N$
- $1 \le Q \le N$
- $1 \le X_1 < X_2 < \ldots < X_Q \le N$
- All inputs are integers.

见题面 Input 部分

见题面 Output 部分