问题描述

最近西西艾弗岛上出入各个场所都要持有一定时限内的核酸检测阴性证明。若在时刻 $t$ 做了核酸检测，则经过 $k$ 个单位时间在时刻 $t+k$ 可以获得结果。若某场所要求持 $c$ 个单位时间内的核酸阴性结果入内，那么凭在时刻 $t$ 做的检测，可以在区间 $[t+k,t+k+c-1]$（包括端点的整数时刻）内进入该场所。

小 $C$ 按时间顺序列出接下来的 $n$ 项出行计划，第 $i$ 项（$1\le i\le n$）表示将在时刻 $t_i$ 进入某场所，该场所要求持 $c_i$ 个单位时间内的核酸检测结果入内（$0 < c_i\le 2\times 10^5$）。

现在有若干次独立查询：如果在时刻 $q$ 做了核酸检测，那么有多少项出行计划的核酸要求可以得到满足？共有 $m$ 个查询 $q_1,q_2,\dots,q_m$，查询之间互不影响。

对于一个给定的查询时刻 $q$，第 $i$ 项出行计划能被满足的条件是

$$q+k \le t_i \le q+k+c_i-1.$$

请对每个查询输出满足条件的出行计划数目。

输入格式

第一行包含三个正整数 $n,m,k$，分别表示出行计划数、查询个数和等待核酸检测结果所需的时间。 接下来 $n$ 行，每行包含两个正整数 $t_i,c_i$，表示一项出行计划；出行计划按时间顺序给出，满足

$$0 < t_1 \le t_2 \le \cdots \le t_n \le 2\times 10^5. $$

最后 $m$ 行，每行一个正整数 $q_j$，表示一次查询；$m$ 个查询也按时间顺序给出，满足

$$0 < q_1 < q_2 < \cdots < q_m \le 2\times 10^5.$$

输出格式

输出共 $m$ 行，第 $j$ 行输出一个整数，表示在时刻 $q_j$ 做检测时可以满足的出行计划数目。

输入样例

6 2 10
5 24
10 24
11 24
34 24
35 24
35 48
1
2

输出样例

3
3

说明

样例解释

• 对查询 $q=1$：$q+k=11$。满足条件的计划为第 $3$ 项（$t_3=11$，窗口 $[11,34]$）、第 $4$ 项（$t_4=34$，窗口 $[11,34]$）和第 $6$ 项（$t_6=35$，窗口 $[11,57]$），共 $3$ 项。
• 对查询 $q=2$：$q+k=12$。满足条件的计划为第 $4$、$5$、$6$ 项（第 $4$、$5$ 项的窗口为 $[12,35]$，第 $6$ 项窗口为 $[12,59]$），共 $3$ 项。

数据范围

• $40\%$ 的数据满足：$1 \le n,k\le 1000$，且 $m=1$；
• $70\%$ 的数据满足：$1 \le n,m,k\le 1000$；
• 全部数据满足：$1 \le n,m,k\le 10^5$。