T255743 [CZOI2023] 纯爱


Umy 终于和 Merry 结婚了！纯爱之神 嘤红（Purelilylove）忠实的记录了她们之间的坎坷的感情（指如上作死片段。 假如 Merry小姐 对 Umy 的好感度可以数值化，当这个值达到 $L$ 时 她就会被 Umy 推倒，愿意和她永远在一起（事实上她已经这样了）。Umy 和 Merry 呆在一起的每一天，都会以增幅 $v$ 匀速增加 Merry 对她的好感度（**由于是匀速，故经过 $1/2$ 天将能增加 $v/2$ 的好感度**）。 然而，Umy 有时笨手笨脚，总会惹 Merry 生气，这时 Merry 对 Umy 的好感度就会下降。嘤红 打算把这一段美好的感情经历记在自己的魔法书上，可是由于磕糖磕的太兴奋了，一不小心记在了妖怪书上。妖怪书有自己的意识，**他调皮的伪造了一部分感情经历**，并且只愿意告诉你她们在经历了 $t$ 天后成功的在一起了。 矛盾在妖怪书上的记录形式为 $n$ 个二元序列 $(a_i,b_i)$ 。表示他们的好感度**第一次**达到 $a_i$ 时，矛盾触发，好感度下降到 $b_i$。 例如，现在有以下序列： 序列 $1$：$a_1=4$，$b_1=1$； 序列 $2$：$a_2=5$，$b_2=0$； 序列 $3$：$a_3=5$，$b_3=2$； 序列 $4$：$a_4=5$，$b_4=3$。 假设 Merry 对 Umy 的好感度每日增幅 $v=1$ ，步入至高殿堂的好感度 $L=6$ ，则这段坎坷（~~好磕~~）的爱情存在这样的过程： 首先用 $4$ 天时间好感度达到 $4$。 根据 序列 $1$ 中记录的矛盾，好感度降低 $3$，现变为 $1$。 经过 Umy 的努力再用 $3$ 天使得好感度到达 $4$，然而因为是第二次到达，序列 $1$ 所记录的矛盾并不再次生效了。 用 $2$ 天好感度达到 $5$。 根据 序列 $2$ 的矛盾的记录，Merry 对 Umy 的好感度清零。 Umy 只好再次用 $5$ 天时间重新使好感度回到了 $5$，但根据序列 $3$，好感度变为 $2$。 再次用了 $3$ 天，好感度达到 $5$。但因为序列 $4$ 是伪造的，所以这个矛盾并不生效。 最后经过一天，好感度变为 $6$。Merry 花费的总时间为 $18$ 天。 嘤红 很喜欢这对小情侣，他希望她们的矛盾可以越少越好。现在，妖怪书给出了一个记录组，并且给出了许多不同的时间 $t$ 。嘤红 很头疼，只好来问你。对于对于第 $i$ 个询问 $t_i$ ，嘤红想知道，她们之间最少需要发生几次矛盾，可以满足 Umy 完全攻略 Merry 所用的时间要**大于** $t_i$。

第一行三个整数 $n$，$L$，$v$ 分别表示妖怪书一共记录了多少次矛盾，Umy 完全攻略 Merry 所需的好感度，以及每天好感度的增幅。 接下来 $n$ 行，每行两个整数，分别代表 $a_i$，$b_i$。 第 $n+1$ 行有一个整数 $q$ 表示询问个数。 接下来 $q$ 行每行一个整数，分别表示 $t_i$。

输出 $q$ 行，每行恰好一个整数，第 $i$ 行的整数对应第 $i$ 个询问的答案。$(1≤i≤q)$。 如果你无论如何都不能使 Umy 使用的天数大于 $t_i$，请输出 `kdl`。

**样例一说明** 1. 不产生任何矛盾，Umy 只需要两天就可以攻略掉 Merry。 1. 如果只产生了 序列 $3$ 的矛盾，她们就需要 $\frac{5}{3}+\frac{6}{3}$ 天才能在一起。 1. 如果同时产生了 序列 $2$ 和 序列 $3$ 的矛盾，就需要 $\frac{4}{3}+\frac{4}{3}+\frac{6}{3}$ 天步入至高殿堂。 1. 不可能超过五天了 Umy 还没攻略掉 Merry，磕到了磕到了。 **数据规模及约定** 对于 $30\%$ 的数据：$1≤n,q≤100$ 对于 $50\%$ 的数据：$1≤n,q≤1000$ 对于 $100\%$ 的数据：$1≤n,q≤10^6$，$1≤L,v,ai,bi≤2^{31}-1$，且保证 $b_i≤a_i$。 测试点#6和测试点#7的时限为500ms，保证复杂度正确的算法可以通过。 **提示** 题目描述中黑体字是你需要特别注意的。