题目描述

学校节日即将到来，学生会计划举办一次大型庆祝活动。Katya 被安排去制作蛋糕。

每个蛋糕必须恰好有 $K$ 层，并且满足如下条件：每一层的直径必须比它正上方那一层的直径至少大 $C$。

例如，当 $C=2$ 时，直径为 $6$ 的蛋糕层上方，只能放置直径不超过 $4$ 的蛋糕层。

Katya 有 $N$ 个圆形蛋糕模具，直径分别为：

她不太擅长烘焙，因此每个模具使用一次后就不能再用了。于是她已经用每个模具各烤出了一个蛋糕层。

遗憾的是，因为准备过程太混乱，Katya 忘记了学生会要求的 $K$ 的具体值。

由于朋友们暂时联系不上，她现在希望对每个 $K\in[L,R]$，都知道最多能用现有蛋糕层做出多少个满足要求的 $K$ 层蛋糕。

请编写程序 cakes 回答 Katya 的问题。

输入格式

第一行输入两个整数 $N,C$。

第二行输入两个整数 $L,R$。

第三行输入 $N$ 个整数 $a_1,a_2,\ldots,a_N$，表示所有蛋糕层的直径。

输出格式

在一行中输出 $R-L+1$ 个非负整数，分别表示当：

时，最多能制作的蛋糕数量。

数据范围

• $1\le N\le 10^5$；
• $1\le L\le R\le N$；
• $0\le C\le 10^9$；
• $1\le a_i\le 10^9$。

子任务

只有当某个子任务的所有测试点都通过时，才能获得该子任务分数。

样例

输入

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

输出

8 4 2 2 0 0 0 0

样例解释

当 $K=1$ 时，可以做 $8$ 个一层蛋糕：

当 $K=2$ 时，可以做 $4$ 个两层蛋糕，例如：

当 $K=3$ 时，可以做 $2$ 个三层蛋糕，例如：

当 $K=4$ 时，也可以做 $2$ 个四层蛋糕，例如：

更大的 $K$ 无法制作任何满足要求的蛋糕。