题目描述

本题输入输出量较大，请选用较为快速的输入输出方式。

现在有 $n+1$ 个位置，编号分别为 $0,1,2,\dots,n$，小 C 会从 $0$ 出发，并在事先确定一个数 $d$，之后每次小 C 都会从它自己的位置 $i$ 跳到 $i+d$，同时还会有 $m$ 种奖品，第 $i$ 种奖品散落在编号在 $[l_i,r_i]$ 内的所有位置，每次跳到一个位置小 C 就可以拿走该位置的所有奖品。

虽然小 C 可以直接令 $d=1$ 这样就可以拿到所有奖品，但是好奇的小 C 还是想知道对于某个 $d$，他能拿到多少种不同的奖品？小 C 会进行这样的询问 $q$ 次，你能帮帮他吗？

输入格式

第一行三个整数 $n,m,q$。

接下来 $m$ 行，第 $i$ 行两个整数 $l_i,r_i$。

接下来 $q$ 行，每行一个整数 $d$。

输出格式

对于每次询问，输出一行表示答案。

输入样例

5 5 5
4 5
1 2
5 5
1 2
1 5
1
2
3
4
5

输出样例

5
4
1
2
3

输入样例 #2

1 2 1
1 1
1 1
1

输出样例 #2

2

输入样例 #3

2 4 2
2 2
2 2
2 2
1 2
1
1

输出样例 #3

4
4

说明提示

【样例解释】

当 $d=1$ 时，显然小 C 会取走所有物品，故答案为 $5$。

当 $d=2$ 时，小 C 会跳到编号分别为 $2,4$ 的格子上，拿走奖品的种类分别为 $1,2,4,5$，故答案为 $4$。

当 $d=3$ 时，小 C 会跳到编号为 $3$ 的格子上，拿走奖品的种类为 $5$，故答案为 $1$。

当 $d=4$ 时，小 C 会跳到编号为 $4$ 的格子上，拿走奖品的种类分别为 $1,5$，故答案为 $2$。

当 $d=5$ 时，小 C 会跳到编号为 $5$ 的格子上，拿走奖品的种类分别为 $1,3,5$，故答案为 $3$。

【其它样例】

所有样例包含在文件夹 jump 中，其中：

• ex_jump1.in/out 为样例组 #1。

• ex_jump2.in/out 满足测试点编号 $1$ 的限制。

【数据范围】

对于全部测试点，$1\le d\le n\le 3\times 10^5,1\le q\le 3\times 10^5,1\le m\le 6\times 10^5,1\le l_i\le r_i\le n$，每个测试点 $10$ 分。