Benson the Rabbit 现在要造一架飞机！

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

为了完成任务 $i$，Benson 需要按顺序运行机器 $l[i], l[i] + 1, \dots, r[i]$。一旦一台机器运行结束，下一台机器立即开始。一旦任务 $i$ 完成，Benson 会立即开始任务 $i+1$，直到任务 $m$ 完成。

为了符合安全规定，工厂必须设定一个安全值 $s$。如果一台机器在过去 $s$ 天或更久之前没有运行过，那么这台机器在运行前必须进行检查。机器在第一次运行时不需要检查。详情请参阅样例。

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

输入格式

你的程序必须从标准输入读取数据。

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

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

最后一行包含 $q$ 个空格分隔的整数 $s[1], s[2], \dots, s[q]$，表示需要测试的 $q$ 个安全值。

输出格式

你的程序必须打印到标准输出。

输出一行包含 $q$ 个空格分隔的整数，第 $j$ 个整数表示当安全值为 $s[j]$ 时需要进行的检查次数。

子任务

对于所有测试用例，输入满足以下范围：

• $1 \le n, m, q \le 200\,000$
• $1 \le l[i] \le r[i] \le n$
• $0 \le s[j] \le 10^{12}$

你的程序将在满足以下限制的输入实例上进行测试：

样例

样例输入 1

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

样例输出 1

3 2 2 2 1 0 0

说明 1

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

样例输入 2

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

样例输出 2

15 14 12 9 5 0 0