AT_abc463_c.Tallest at the Moment

Currently, there are $N$ Takahashi in a conference room. The $i$-th $(1\le i\le N)$ Takahashi has a height of $H _ i$ and will leave the room $L _ i$ minutes from now. Once a Takahashi leaves the room, he never returns.

You are given $Q$ queries, so answer them in order. For the $i$-th $(1\le i\le Q)$ query, you are given an integer $T _ i$, so find the maximum height among the Takahashi who are in the room $T _ i+\dfrac12$ minutes from now. Under the constraints of this problem, it is guaranteed that at least one Takahashi will be in the room $T _ i+\dfrac12$ minutes from now.

目前，会议室内有 $N$ 个高桥。第 $i$ 个（$1\le i\le N$）高桥身高为 $H _ i$，将在 $L _ i$ 分钟后离开房间。一旦某个高桥离开房间，他就不会再返回。

你将收到 $Q$ 个查询，请按顺序回答它们。对于第 $i$ 个（$1\le i\le Q$）个查询，给定一个整数 $T _ i$，请找出在 $T _ i+\dfrac12$ 分钟后仍在房间内的所有高桥中的最大身高。在本题的约束条件下，保证在 $T _ i+\dfrac12$ 分钟后，房间内至少还剩一名高桥。

The input is given from Standard Input in the following format:

$N$
$H _ 1$ $L _ 1$
$H _ 2$ $L _ 2$
$\vdots$
$H _ N$ $L _ N$
$Q$
$T _ 1$ $T _ 2$ $\ldots$ $T _ Q$

输入从标准输入中按以下格式给出：

$N$
$H _ 1$ $L _ 1$
$H _ 2$ $L _ 2$
$\vdots$
$H _ N$ $L _ N$
$Q$
$T _ 1$ $T _ 2$ $\ldots$ $T _ Q$

Output $Q$ lines. The $i$-th line $(1\le i\le Q)$ should contain the answer to the $i$-th query.

输出 $Q$ 行。第 $i$ 行（$1\le i\le Q$）应包含第 $i$ 个查询的答案。

Sample 1 Explanation:
$3+\dfrac12$ minutes from now, all Takahashi currently in the room are still there. Thus, the answer to the first query is $31$, the maximum of $\lbrace31,26,3,15\rbrace$.

$5+\dfrac12$ minutes from now, only the fourth Takahashi is in the room. Thus, the answer to the third query is $15$, the maximum of $\lbrace15\rbrace$.

Constraints

• $1\le N\le3\times10 ^ 5$
• $1\le H _ i\le10 ^ 9\ (1\le i\le N)$
• $1\le L _ 1\le L _ 2\le\cdots\le L _ N\le10 ^ 9$
• $1\le Q\le3\times10 ^ 5$
• $0\le T _ i\lt L _ N\ (1\le i\le Q)$
• All input values are integers.

样例 1 解释：
从现在起 $3+\dfrac12$ 分钟后，房间内所有当前存在的高桥仍留在房间中。因此，第一个查询的答案为 $31$，即集合 $\lbrace31,26,3,15\rbrace$ 中的最大值。

从现在起 $5+\dfrac12$ 分钟后，房间内仅剩第四位高桥。因此，第三个查询的答案为 $15$，即集合 $\lbrace15\rbrace$ 中的最大值。

约束条件

• $1\le N\le3\times10 ^ 5$
• $1\le H _ i\le10 ^ 9\ (1\le i\le N)$
• $1\le L _ 1\le L _ 2\le\cdots\le L _ N\le10 ^ 9$
• $1\le Q\le3\times10 ^ 5$
• $0\le T _ i\lt L _ N\ (1\le i\le Q)$
• 所有输入值均为整数。