护照是全世界旅行者进入外国时使用的证件。

在一个星球上，有 $N$ 个国家，编号从 $1$ 到 $N$。每个国家都会签发护照。当旅行者持有国家 $i$ ($1 \le i \le N$) 签发的护照时，他可以进入国家 $L_i, L_i + 1, \dots, R_i$。这里保证旅行者可以进入签发护照的国家，即满足 $L_i \le i \le R_i$。

你有一位喜欢旅行的朋友。虽然他梦想环游世界，但他起初并没有护照。因此，他计划通过重复以下两个动作来访问所有 $N$ 个国家：

• 获取他当前所在国家签发的护照。
• 移动到他当前持有的护照可以进入的国家。

当你听说他的计划时，你想知道这个计划是否可以实现，如果可以，他最少需要获取多少本护照。由于你不知道他住在哪里，你考虑了他可能居住的 $Q$ 个国家 $X_1, X_2, \dots, X_Q$。

请编写一个程序，给定护照信息和他可能居住的国家，对于每种可能性，判断他是否能够访问所有 $N$ 个国家，如果可以，计算他最少需要获取的护照数量。

输入格式

从标准输入读取以下数据：

$N$ $L_1 \ R_1$ $L_2 \ R_2$ $\vdots$ $L_N \ R_N$ $Q$ $X_1$ $X_2$ $\vdots$ $X_Q$

输出格式

向标准输出写入 $Q$ 行。第 $j$ 行 ($1 \le j \le Q$) 对应你的朋友住在国家 $X_j$ 的情况。如果他能够访问所有 $N$ 个国家，则该行应包含他最少需要获取的护照数量。否则，该行应包含 $-1$。

数据范围

• $2 \le N \le 200\,000$
• $1 \le L_i \le i \le R_i \le N$ ($1 \le i \le N$)
• $1 \le Q \le N$
• $1 \le X_j \le N$ ($1 \le j \le Q$)
• $X_j < X_{j+1}$ ($1 \le j \le Q - 1$)
• 给定值均为整数。

子任务

1. (6 分) $Q = 1, X_1 = 1$。
2. (16 分) $N \le 300, Q = 1$。
3. (24 分) $N \le 2\,500, Q = 1$。
4. (8 分) $N \le 2\,500$。
5. (46 分) 无附加限制。

样例

样例 1

输入：

4
1 3
2 4
2 3
4 4
1
1

输出：

2

样例 2

输入：

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

输出：

4

样例 3

输入：

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

输出：

-1
2
1
2
-1

样例 4

输入：

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

输出：

-1
-1
-1
-1