题目描述

我们有一个由两个灯泡组成的沙漏，灯泡A和灯泡B。这些灯泡中装有一些沙子。当我们放置沙漏时，要么灯泡 $A$ 覆盖在另一个灯泡上方并成为 上部灯泡 ，要么灯泡A覆盖在另一个灯泡下方并成为 下部灯泡。

沙子以每秒1克的速度从上部灯泡掉落到下部灯泡。当上部灯泡不再含有任何沙子时，就什么也不会发生。

初始时刻 $0$，灯泡A是上部灯泡，其中含有 $a$ 克沙子；灯泡B含有 $X-a$ 克沙子（总共 $X$ 克）。

我们将在 $r_1,r_2,..,r_K$ 时刻翻转沙漏。假设这是瞬时动作且不需要时间。这里，时间 $t$ 指的是离初始时刻 $0$ 秒后的时间。

给定 $Q$ 个查询。每个查询的形式为 $(t_i,a_i)$。对于每个查询，假设 $a=a_i$，找出在时刻 $t_i$ 灯泡A中包含的沙子的数量。

约束条件

• $1 \leq X \leq 10^9$
• $1 \leq K \leq 10^5$
• $1 \leq r_1 < r_2 < .. < r_K \leq 10^9$
• $1 \leq Q \leq 10^5$
• $0 \leq t_1 < t_2 < .. < t_Q \leq 10^9$
• $0 \leq a_i \leq X (1 \leq i \leq 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

在第一个查询中，初始的 90 克沙子中的 30 克将从灯泡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