分数: 700 点
问题陈述
我们有一个沙漏,由两个灯泡组成:灯泡 A 和灯泡 B。这些灯泡含有一定量的沙子。 当我们放置沙漏时,任一灯泡 A or B 位于另一个之上并成为 上部灯泡。另一个灯泡成为 下灯泡.
沙子从上球到下球的速度为 1 克每秒。 当上部球茎不再含有任何沙子时,什么也不会发生。
最初时间 0,灯泡 A 是上面的灯泡,包含 a 克沙;灯泡 B 包含 X-a 克沙子(总共 X 克)。
我们会及时翻沙漏 r_1,r_2,..,r_K。假设这是一个瞬时动作,不需要时间。在这里,时间 t 参考时间 t 时间后的秒数 0.
你被给予 Q 查询。 每个查询的形式为 (t_i,a_i)。 对于每个查询,假设 a=a_i 并找出此时球茎 A 中所含沙子的量 t_i.
约束
- 1≤X≤10^9
- 1≤K≤10^5
- 1≤r_1<r_2< .. <r_K≤10^9
- 1≤Q≤10^5
- 0≤t_1<t_2< .. <t_Q≤10^9
- 0≤a_i≤X (1≤i≤Q)
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
X K r_1 r_2 .. r_K Q t_1 a_1 t_2 a_2 : t_Q a_Q
输出
对于每个查询,在其自己的行中打印答案。
示例输入 1
180 3 60 120 180 3 30 90 61 1 180 180
示例输出 1
60 1 120
在第一个查询中, 30 出初始 90 克沙子将从灯泡 A 上掉落,导致 60 克。 在第二个查询中,初始 1 克沙子将从灯泡 A 中掉落,接下来不会发生任何事情 59 秒。然后,我们将沙漏翻过来, 1 此后第二个,灯泡 A 包含 1 当时有问题的沙子克数。
示例输入 2
100 1 100000 4 0 100 90 100 100 100 101 100
示例输出 2
100 10 0 0
在每个查询中,上面的灯泡最初包含 100 克,在我们翻转沙漏之前问题就出现了。
示例输入 3
100 5 48 141 231 314 425 7 0 19 50 98 143 30 231 55 342 0 365 100 600 10
示例输出 3
19 52 91 10 58 42 100