← 返回题目列表

AtCoder · arc082_d

F. 沙漏

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

分数: 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