← 返回题目列表

AtCoder · abc463_c

C. 目前最高

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

目前,有 N 高桥在会议室。 的 i-th (1\le i\le N) 高桥的身高为 H _ i 并将离开房间 L _ i 分钟后。 高桥一旦离开房间,就再也不会回来。

你被给予 Q 有疑问,请按顺序回答。 对于 i-th (1\le i\le Q) 查询,给你一个整数 T _ i,所以找到房间里的高桥的最大高度 T _ i+\dfrac12 分钟后。 在这个问题的约束下,保证房间里至少有一个高桥 T _ i+\dfrac12 分钟后。

约束

  • 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)
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

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

输出

输出 Q 行。 的 i第行 (1\le i\le Q) 应包含以下问题的答案 i-第一个查询。


示例输入 1

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

示例输出 1

31
26
15
15

3+\dfrac12 几分钟后,房间里的所有高桥都还在那里。 因此,第一个查询的答案是 31,最大值 \lbrace31,26,3,15\rbrace.

5+\dfrac12 几分钟后,房间里就只有第四个高桥了。 因此,第三个查询的答案是 15,最大值 \lbrace15\rbrace.


示例输入 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