题目描述

兔子 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$ 时，所需检查机器的次数。

5 3 7
1 3
3 5
2 3
0 1 2 3 4 5 6

3 2 2 2 1 0 0 

6 6 7
1 6
1 5
1 4
1 3
1 2
1 1
1 2 3 4 5 6 7

15 14 12 9 5 0 0 

提示

样例 #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$ 天被安全检查。

数据范围

对于 $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}$

注：由于洛谷限制，数据不完全按照原题分配子任务。