AT_abc463_c [ABC463C] 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.

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 $

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

### Sample Explanation 1 $ 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.