题目描述

期末周的自习室里坐着 $N$ 名同学。第 $i$ 名同学 $(1 \le i \le N)$ 的身高是 $H_i$ 厘米，他会在从现在起第 $L_i$ 分钟离开自习室，一旦离开就不再回来。

输入保证 $L_1 \le L_2 \le \cdots \le L_N$，即同学们已按离开时间从早到晚排好序。

管理员小明会在若干个时刻巡视自习室。他一共巡视 $Q$ 次，第 $i$ 次巡视发生在从现在起第 $T_i + \frac{1}{2}$ 分钟。请你对每次巡视，回答此刻还留在自习室的同学中身高的最大值。

题目保证每次巡视时，自习室里至少还有 $1$ 名同学。

巡视时刻带 $+\frac{1}{2}$，是为了避免「第 $L_i$ 分钟这一瞬间人到底算不算还在」的歧义。

输入格式

第一行一个整数 $N$，表示同学人数。

接下来 $N$ 行，第 $i$ 行两个整数 $H_i, L_i$，表示第 $i$ 名同学的身高与离开时刻。

接下来一行一个整数 $Q$，表示巡视次数。

最后一行 $Q$ 个整数 $T_1, T_2, \ldots, 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 解释

一名第 $L$ 分钟离开的同学，在第 $T+\frac12$ 分钟时还在，当且仅当 $L > T$。

• 第 1 次巡视 $T=3$：四人离开时刻 $4,5,5,9$ 都大于 $3$，全都还在，最大身高 $31$。
• 第 2 次巡视 $T=4$：第 1 人离开时刻 $4$，不满足 $4>4$，已经走了；剩下 $(26,5),(3,5),(15,9)$，最大身高 $26$。
• 第 3 次巡视 $T=5$：离开时刻为 $4,5,5$ 的三人都已走，只剩 $(15,9)$，答案 $15$。
• 第 4 次巡视 $T=6$：同上，仍只剩 $(15,9)$，答案 $15$。

请特别注意第 2 次巡视：离开时刻恰好等于 $T$ 的同学已经离开。

样例 2 输入

5
100 7
50 7
80 7
20 7
60 7
2
0 6

样例 2 输出

100
100

样例 2 解释

所有同学的离开时刻都是 $7$。$T=0$ 与 $T=6$ 时都满足 $7 > T$，五人全在，最大身高为 $100$。

这个样例提醒：离开时刻可以大量重复，查找边界要想清楚。

数据范围与提示

对于所有测试数据，保证 $1 \le N \le 3\times10^5$，$1 \le H_i \le 10^9$，$1 \le L_1 \le L_2 \le \cdots \le L_N \le 10^9$，$1 \le Q \le 3\times10^5$，$0 \le T_i < L_N$，所有输入均为整数。

测试点编号	$N, Q$ 的范围	特殊性质
$1 \sim 3$	$N, Q \le 1000$	无
$4 \sim 5$	$N, Q \le 10^5$	所有 $L_i$ 互不相同
$6 \sim 7$		无
$8 \sim 10$	$N, Q \le 3\times10^5$