题目描述

现在会议室里有 $N$ 个高橋君。第 $i$ 个高橋君 $(1 \le i \le N)$ 的身高是 $H_i$，他将在从现在起第 $L_i$ 分钟离开会议室。一旦离开，就再也不会回来。

题目保证 $L_1 \le L_2 \le \cdots \le L_N$，也就是输入已经按离开时间从早到晚排好序了。

给出 $Q$ 个询问，请依次回答。第 $i$ 个询问 $(1 \le i \le Q)$ 给出一个整数 $T_i$，请回答：从现在起第 $T_i + \dfrac{1}{2}$ 分钟时，还留在会议室里的高橋君中，身高的最大值是多少。

题目保证在本题的约束下，第 $T_i + \dfrac{1}{2}$ 分钟时会议室里至少还有 $1$ 个高橋君。

输入格式

N
H_1 L_1
H_2 L_2
...
H_N L_N
Q
T_1 T_2 ... T_Q

输出格式

输出 $Q$ 行，第 $i$ 行是第 $i$ 个询问的答案。

输入示例 1

4
31 4
26 5
3 5
15 9
4
3 4 5 6

输出示例 1

31
26
15
15

示例 1 说明

询问的时刻都带着 $+\dfrac{1}{2}$，所以「第 $L$ 分钟离开」的人，在 $T + \dfrac{1}{2}$ 时刻还在当且仅当 $L > T$。

• $T_1 = 3$：$3 + \dfrac{1}{2}$ 时刻，$4$ 个人的离开时间 $4, 5, 5, 9$ 都大于 $3$，全都还在。最大身高是 $\{31, 26, 3, 15\}$ 中的 $31$。
• $T_2 = 4$：离开时间为 $4$ 的第 $1$ 个人已经走了，剩下 $\{26, 3, 15\}$，最大是 $26$。
• $T_3 = 5$：离开时间为 $4, 5, 5$ 的三人都走了，只剩第 $4$ 个人，答案 $15$。
• $T_4 = 6$：同样只剩第 $4$ 个人，答案 $15$。

输入示例 2

10
587 138
772 155
755 404
519 408
529 432
169 586
114 632
249 656
329 972
299 984
14
443 801 824 276 399 314 300 510 311 580 498 930 359 5

输出示例 2

329
329
329
755
755
755
755
329
755
329
329
329
755
772

示例 2 说明

以最后一个询问 $T = 5$ 为例：所有人的离开时间最小是 $138$，都大于 $5$，所以 $10$ 个人全都还在，最大身高是 $772$。

以第一个询问 $T = 443$ 为例：离开时间 $\le 443$ 的前 $5$ 个人（$138, 155, 404, 408, 432$）都已离开，剩下的人身高为 $\{169, 114, 249, 329, 299\}$，最大是 $329$。

约束条件

• $1 \le N \le 3 \times 10^5$
• $1 \le H_i \le 10^9 \ (1 \le i \le N)$
• $1 \le L_1 \le L_2 \le \cdots \le L_N \le 10^9$
• $1 \le Q \le 3 \times 10^5$
• $0 \le T_i < L_N \ (1 \le i \le Q)$
• 所有输入值均为整数