310243: CF1804B. Vaccination

B. Vaccinationtime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

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?

Input

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$.

Output

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

ExampleInput

5
6 3 5 3
1 2 3 10 11 18
6 4 0 0
3 3 3 3 3 4
9 10 2 2
0 1 2 3 4 5 6 7 8
3 10 3 6
10 20 30
5 5 4 4
0 2 4 6 8

Output

2
3
2
3
1

Note

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.

题目大意：
伊森运营着一个疫苗接种站，帮助人们对抗季节性流感。他分析历史数据以制定疫苗使用的最佳策略。

考虑有 n 个病人在特定的一天来到接种站。第 i 个病人在时刻 t_i 到达。我们知道每个病人最多只能等待 w 个时间点。这意味着可以在时刻 t_i, t_i + 1, ..., t_i + w 给第 i 个病人接种疫苗。

疫苗以每包 k 剂的形式出现。每个病人需要恰好一剂。疫苗包存放在特殊的冰箱中。从冰箱中取出并打开一个包后，它就不能再放回去了。疫苗在冰箱外的寿命是 d 个时间点。因此，如果在时刻 x 从冰箱中取出并打开一个包，它的剂量可以在时刻 x, x + 1, ..., x + d 用于接种疫苗。在时刻 x + d + 1，这个包中所有剩余未使用的剂量都会被扔掉。

假设接种站有足够的员工在每个时刻进行任意数量的操作。求接种所有 n 个病人所需的最少疫苗包数量。

输入输出数据格式：
输入：
第一行包含测试用例的数量 t (1 ≤ t ≤ 10^4)。然后是 t 个测试用例的描述。
每个测试用例的第一行包含四个整数 n, k, d 和 w (1 ≤ n, k ≤ 2 * 10^5, 0 ≤ d, w ≤ 10^6)。它们分别是病人数量、每包疫苗的剂量数量、疫苗在冰箱外可以存活的时间点数量以及每个病人可以等待的时间点数量。
每个测试用例的第二行包含一个非递减序列 t_1, t_2, ..., t_n (0 ≤ t_1 ≤ t_2 ≤ ... ≤ t_n ≤ 10^6)。序列的第 i 个元素是第 i 个病人到达接种站的时刻。
保证所有测试用例的 n 之和不超过 2 * 10^5。

输出：
输出一个整数，表示接种所有 n 个病人所需的最少疫苗包数量。

示例：
输入：
```
5
6 3 5 3
1 2 3 10 11 18
6 4 0 0
3 3 3 3 3 4
9 10 2 2
0 1 2 3 4 5 6 7 8
3 10 3 6
10 20 30
5 5 4 4
0 2 4 6 8
```
输出：
```
2
3
2
3
1
```题目大意： 伊森运营着一个疫苗接种站，帮助人们对抗季节性流感。他分析历史数据以制定疫苗使用的最佳策略。 考虑有 n 个病人在特定的一天来到接种站。第 i 个病人在时刻 t_i 到达。我们知道每个病人最多只能等待 w 个时间点。这意味着可以在时刻 t_i, t_i + 1, ..., t_i + w 给第 i 个病人接种疫苗。 疫苗以每包 k 剂的形式出现。每个病人需要恰好一剂。疫苗包存放在特殊的冰箱中。从冰箱中取出并打开一个包后，它就不能再放回去了。疫苗在冰箱外的寿命是 d 个时间点。因此，如果在时刻 x 从冰箱中取出并打开一个包，它的剂量可以在时刻 x, x + 1, ..., x + d 用于接种疫苗。在时刻 x + d + 1，这个包中所有剩余未使用的剂量都会被扔掉。 假设接种站有足够的员工在每个时刻进行任意数量的操作。求接种所有 n 个病人所需的最少疫苗包数量。 输入输出数据格式： 输入： 第一行包含测试用例的数量 t (1 ≤ t ≤ 10^4)。然后是 t 个测试用例的描述。 每个测试用例的第一行包含四个整数 n, k, d 和 w (1 ≤ n, k ≤ 2 * 10^5, 0 ≤ d, w ≤ 10^6)。它们分别是病人数量、每包疫苗的剂量数量、疫苗在冰箱外可以存活的时间点数量以及每个病人可以等待的时间点数量。 每个测试用例的第二行包含一个非递减序列 t_1, t_2, ..., t_n (0 ≤ t_1 ≤ t_2 ≤ ... ≤ t_n ≤ 10^6)。序列的第 i 个元素是第 i 个病人到达接种站的时刻。 保证所有测试用例的 n 之和不超过 2 * 10^5。 输出： 输出一个整数，表示接种所有 n 个病人所需的最少疫苗包数量。 示例： 输入： ``` 5 6 3 5 3 1 2 3 10 11 18 6 4 0 0 3 3 3 3 3 4 9 10 2 2 0 1 2 3 4 5 6 7 8 3 10 3 6 10 20 30 5 5 4 4 0 2 4 6 8 ``` 输出： ``` 2 3 2 3 1 ```