题目描述

译自 NOISG 2023 Final T2. Inspections

兔子本森现在需要建造一架飞机！

本森的工厂有 $n$ 台机器，编号从 $1$ 到 $n$。每台机器运行一天，且同一时间只能运行一台机器。他有 $m$ 个任务需要完成，编号从 $1$ 到 $m$。每个任务 $i$ 由两个正整数 $l[i]$ 和 $r[i]$ 表示，其中 $l[i] \leq r[i]$。

要完成任务 $i$，本森需要按顺序运行机器 $l[i], l[i]+1, \ldots, r[i]$。一台机器运行结束后，下一台机器立即开始运行。完成任务 $i$ 后，本森立即开始任务 $i+1$，直到完成任务 $m$。

为了遵守安全规定，工厂必须设定一个安全值 $s$。如果一台机器的安全值为 $s$，且在过去 $s$ 天或更长时间内未运行，则该机器在运行前需要检查。机器首次运行时无需检查。详见示例说明。

本森有 $q$ 个不同的候选安全值 $s[1], s[2], \ldots, s[q]$。对于每个安全值 $s[j]$，帮助他计算若安全值为 $s[j]$ 时需要进行的检查次数。

输入格式

程序需从标准输入读取数据。

输入的第一行包含三个空格分隔的整数 $n, m, q$，分别表示机器数量、任务数量和安全值数量。

接下来的 $m$ 行，每行包含两个空格分隔的整数，分别为 $l[i]$ 和 $r[i]$，描述任务 $i$。

下一行包含 $q$ 个空格分隔的整数 $s[1], s[2], \ldots, s[q]$，表示待测试的 $q$ 个安全值。

输出格式

程序需向标准输出输出结果。

输出一行，包含 $q$ 个空格分隔的整数，第 $j$ 个整数表示若安全值为 $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

机器将按以下顺序运行：$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$ 天检查。

这个样例满足子任务 $1,2,4,5$ 的限制。

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 \leq n, m, q \leq 200000$
• $1 \leq l[i] \leq r[i] \leq n$
• $0 \leq s[j] \leq 10^{12}$

详细子任务附加限制及分值如下表所示：