CF1804B.Vaccination

Ethan runs a vaccination station to help people combat the seasonal flu. He analyses the historical data in order to develop an optimal strategy for vaccine usage.

Consider there are $n$ patients coming to the station on a particular day. The $i$-th patient comes at the moment $t_i$. We know that each of these patients can be asked to wait for no more than $w$ time moments. That means the $i$-th patient can get vaccine at moments $t_i, t_i + 1, \ldots, t_i + w$.

Vaccines come in packs, each pack consists of $k$ doses. Each patient needs exactly one dose. Packs are stored in a special fridge. After a pack is taken out of the fridge and opened, it can no longer be put back. The lifetime of the vaccine outside the fridge is $d$ moments of time. Thus, if the pack was taken out of the fridge and opened at moment $x$, its doses can be used to vaccinate patients at moments $x, x + 1, \ldots, x + d$. At moment $x + d + 1$ all the remaining unused doses of this pack are thrown away.

Assume that the vaccination station has enough staff to conduct an arbitrary number of operations at every moment of time. What is the minimum number of vaccine packs required to vaccinate all $n$ patients?

伊桑运营一家疫苗接种站，以帮助人们抵御季节性流感。他分析历史数据，以制定疫苗使用的最优策略。

假设某天有 $n$ 名患者前来接种站。第 $i$ 名患者在时刻 $t_i$ 到达。已知每名患者最多只能等待 $w$ 个时间单位，即第 $i$ 名患者可在时刻 $t_i,\, t_i + 1,\, \ldots,\, t_i + w$ 接种疫苗。

疫苗以包装形式供应，每包含 $k$ 剂。每名患者恰好需要一剂。疫苗包储存在专用冰箱中。一旦某包疫苗被从冰箱中取出并开封，便不可再放回冰箱。疫苗在冰箱外的有效期为 $d$ 个时间单位。因此，若某包疫苗在时刻 $x$ 被取出并开封，则其内各剂疫苗可用于在时刻 $x,\, x + 1,\, \ldots,\, x + d$ 为患者接种；而在时刻 $x + d + 1$，该包中所有尚未使用的剩余剂量将被丢弃。

假设接种站拥有充足的人手，可在任意时刻执行任意数量的操作。那么，为完成全部 $n$ 名患者的疫苗接种，所需的最少疫苗包数是多少？

The first line of the input contains the number of test cases $t$ ($1 \leq t \leq 10^4$). Then follow $t$ descriptions of the test cases.

The first line of each test case contains four integers $n$, $k$, $d$ and $w$ ($1 \leq n, k \leq 2 \cdot 10^5$, $0 \leq d, w \leq 10^6$). They are the number of patients, the number of doses per vaccine pack, the number of moments of time the vaccine can live outside the fridge, and the number of moments of time each of the patients can wait, respectively.

The second line of each test case contains a non-decreasing sequence $t_1, t_2, \ldots, t_n$ ($0 \leq t_1 \leq t_2 \leq \ldots \leq t_n \leq 10^6$). The $i$-th element of this sequence is the moment when the $i$-th patient comes to the vaccination station.

It is guaranteed that the sum of $n$ over all test cases won't exceed $2 \cdot 10^5$.

输入的第一行包含测试用例的数量 $t$（$1 \leq t \leq 10^4$）。随后是 $t$ 个测试用例的描述。

每个测试用例的第一行包含四个整数 $n$、$k$、$d$ 和 $w$（$1 \leq n, k \leq 2 \cdot 10^5$，$0 \leq d, w \leq 10^6$），分别表示患者人数、每盒疫苗的剂量数、疫苗在冰箱外可保存的时间单位数，以及每位患者所能等待的时间单位数。

每个测试用例的第二行包含一个非递减序列 $t_1, t_2, \ldots, t_n$（$0 \leq t_1 \leq t_2 \leq \ldots \leq t_n \leq 10^6$），其中第 $i$ 个元素 $t_i$ 表示第 $i$ 位患者到达接种点的时刻。

保证所有测试用例的 $n$ 值之和不超过 $2 \cdot 10^5$。

Output one integer, the minimum number of vaccine packs required to vaccinate all $n$ patients.

输出一个整数，即为给全部 $n$ 名患者接种疫苗所需的最少疫苗包数量。

In the first example, the first pack can be opened at moment $1$ to vaccinate patient $1$. The vaccine is durable enough to be used at moments $2$ and $3$ for patients $2$ and $3$, respectively. Then the staff needs to ask patients $4$ and $5$ to wait for moment $13$. At moment $13$ the staff opens the second vaccine pack and serves patients $4$ and $5$. Finally, the last patient comes at moment $18$ and immediately gets the last dose of the second pack while it is still fine.

In the second example, the vaccine should be used exactly at the moment it is taken out of the fridge. Moreover, all the patients want to be served at exactly the same moment they come. That means the staff needs to open two packs at moment $3$ and use five doses on patients $1$, $2$, $3$, $4$, and $5$. There will be three doses left ouf of these two packs but they can't be used for patient $6$. When patient $6$ comes at moment $4$ the staff needs to open a new pack just to use only one dose out of it.

在第一个例子中，第一支疫苗可在时刻 $1$ 开启，用于为患者 $1$ 接种。该疫苗的稳定性足以支持其在时刻 $2$ 和 $3$ 分别用于患者 $2$ 和 $3$。随后，工作人员需让患者 $4$ 和 $5$ 等待至时刻 $13$。在时刻 $13$，工作人员开启第二支疫苗，并为患者 $4$ 和 $5$ 提供接种服务。最后，第六位患者于时刻 $18$ 到达，并立即使用第二支疫苗中剩余的最后一剂（此时该剂仍在有效期内）。

在第二个例子中，疫苗必须在从冰箱中取出的同一时刻即刻使用。此外，所有患者均要求在抵达的同一时刻即刻完成接种。这意味着工作人员必须在时刻 $3$ 同时开启两支疫苗，并将其中五剂分别用于患者 $1$、$2$、$3$、$4$ 和 $5$。这两支疫苗共剩余三剂，但无法用于患者 $6$。当患者 $6$ 于时刻 $4$ 到达时，工作人员必须新开一支疫苗，仅从中使用一剂。