P11534 [NOISG 2023 Finals] Inspections

兔子 Benson 正要造一架飞机！ Benson 的工厂有 $n$ 个机器，由 $1\sim n$ 编号。每台机器会工作一天，且每一天只能有一台机器工作。他需要制造 $m$ 个部件，由 $1\sim m$ 编号。每个部件用两个整数 $l_i, r_i$ 表示，其中 $l_i\leq r_i$。 制造第 $i$ 个部件时，Benson 将依次运行编号为 $l_i, l_i+1,\cdots,r_i$ 的机器。当一台机器结束工作，下一台机器会立即启动。此外，Benson 会依次制造这 $m$ 个部件。当一个部件制造完毕，下一个部件会立即开始制造。 为了保障机器的安全，工厂设有一个检查系数 $s$。若一台机器已经连续 $s$ 或更多天没有启动，那么这次启动前必须对其进行安全检查。特别地，第一次启动某个机器时无需进行安全检查。 Benson 有 $q$ 个询问 $s_1, s_2, \cdots, s_q$。对于每个检查系数 $s_j$，请你帮助他计算完成所有部件所需的检查次数。

第一行三个正整数 $n, m, q$，用空格隔开。 接下来 $m$ 行，每行两个整数 $l_i,r_i$，描述第 $i$ 个部件。 接下来一行 $q$ 个整数 $s_1,s_2,\cdots,s_q$，表示 $q$ 个检查系数。

输出一行 $q$ 个整数，表示当检查系数为 $s_j$ 时，所需检查机器的次数。

#### 样例 #1 解释 Benson 会按照如下顺序启动机器：$1,2,3,3,4,5,2,3$。 第 $4$ 天启动的 $3$ 号机器连续 $0$ 天未启动； 第 $7$ 天启动的 $2$ 号机器连续 $4$ 天未启动； 第 $8$ 天启动的 $3$ 号机器连续 $3$ 天未启动。 当检查系数为 $0$ 时，$3$ 号机器会在第 $4$ 天和第 $8$ 天被安全检查，而 $2$ 号机器会在第 $7$ 天被安全检查。 当检查系数为 $2$ 时，$3$ 号机器会在第 $8$ 天被安全检查，而 $2$ 号机器会在第 $7$ 天被安全检查。 #### 数据范围 | Subtask | 分值 | 特殊限制 | | :-----------: | :-----------: | :-----------: | | $0$ | $0$ | 样例 | | $1$ | $11$ | $n,m,q\leq 200$ | | $2$ | $18$ | $n,m\leq 2000$ | | $3$ | $22$ | $l_i=1$ | | $4$ | $26$ | $m\leq2000$ | | $5$ | $23$ | 无 | 对于 $100\%$ 的数据： - $1\leq n, m,q\leq 2\times 10^5$ - $1\leq l_i\leq r_i\leq n$ - $0\leq s_j\leq 10^{12}$ 注：由于洛谷限制，数据不完全按照原题分配子任务。