题目描述

有一个由部件 A 和部件 B 组成的沙漏。这些部件中都装有一些沙子。当放置沙漏时，部件 A 或部件 B 其中之一会在上方，剩下的会在下方。

每经过 $1$ 秒，$1$ 克的沙子会从上面的部件流到下面的部件。但是，如果上面的部件中已经没有沙子，则不会有沙子落下。

在初始时刻 $0$，部件 A 在上方，部件 A 中有 $a$ 克沙子，部件 B 中有 $X-a$ 克沙子（也就是说，总共一共有 $X$ 克沙子）。

在时刻 $r_1,r_2,\ldots,r_K$ 时，沙漏会被翻转一次。这个操作是瞬间完成的，不消耗时间。这里，时刻 $t$ 指的是从时刻 $0$ 起经过 $t$ 秒的时刻。

现有 $Q$ 个询问。每个询问给定 $(t_i, a_i)$。对于每个询问，当 $a=a_i$ 时，请回答在时刻 $t_i$ 时部件 A 中的沙子的克数。

输入格式

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

$X$ $K$ $r_1$ $r_2$ $\ldots$ $r_K$ $Q$ $t_1$ $a_1$ $t_2$ $a_2$ $\ldots$ $t_Q$ $a_Q$

输出格式

对于每个查询，输出答案，每行一项。

样例 1

输入

180
3
60 120 180
3
30 90
61 1
180 180

输出

60
1
120

样例 2

输入

100
1
100000
4
0 100
90 100
100 100
101 100

输出

100
10
0
0

样例 3

输入

100
5
48 141 231 314 425
7
0 19
50 98
143 30
231 55
342 0
365 100
600 10

输出

19
52
91
10
58
42
100

说明/提示

限制条件

• $1 \leq X \leq 10^9$
• $1 \leq K \leq 10^5$
• $1 \leq r_1 < r_2 < \ldots < r_K \leq 10^9$
• $1 \leq Q \leq 10^5$
• $0 \leq t_1 < t_2 < \ldots < t_Q \leq 10^9$
• $0 \leq a_i \leq X \quad(1 \leq i \leq Q)$
• 所有输入值都是整数。

样例解释 1

对于第 1 个查询，最开始部件 A 中有 $90$ 克沙子，经过 $30$ 秒减少了 $30$ 克，剩下 $60$ 克。 对于第 2 个查询，最开始部件 A 中的 $1$ 克沙子在 $1$ 秒后全部流入 B，之后 $59$ 秒都不会再有变化。此时在 $60$ 秒将沙漏翻转，$1$ 秒后查询部件 A 内的沙子的量，所以答案为 $1$ 克。

样例解释 2

无论哪个查询，最开始部件 A 中都有 $100$ 克沙子，被问的时刻也都在沙漏翻转前。因此结果就是最初数量减去当前时刻值。

由 ChatGPT 5 翻译