310555: CF1851A. Escalator Conversations

A. Escalator Conversationstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

One day, Vlad became curious about who he can have a conversation with on the escalator in the subway. There are a total of $n$ passengers. The escalator has a total of $m$ steps, all steps indexed from $1$ to $m$ and $i$-th step has height $i \cdot k$.

Vlad's height is $H$ centimeters. Two people with heights $a$ and $b$ can have a conversation on the escalator if they are standing on different steps and the height difference between them is equal to the height difference between the steps.

For example, if two people have heights $170$ and $180$ centimeters, and $m = 10, k = 5$, then they can stand on steps numbered $7$ and $5$, where the height difference between the steps is equal to the height difference between the two people: $k \cdot 2 = 5 \cdot 2 = 10 = 180 - 170$. There are other possible ways.

Given an array $h$ of size $n$, where $h_i$ represents the height of the $i$-th person. Vlad is interested in how many people he can have a conversation with on the escalator individually.

For example, if $n = 5, m = 3, k = 3, H = 11$, and $h = [5, 4, 14, 18, 2]$, Vlad can have a conversation with the person with height $5$ (Vlad will stand on step $1$, and the other person will stand on step $3$) and with the person with height $14$ (for example, Vlad can stand on step $3$, and the other person will stand on step $2$). Vlad cannot have a conversation with the person with height $2$ because even if they stand on the extreme steps of the escalator, the height difference between them will be $6$, while their height difference is $9$. Vlad cannot have a conversation with the rest of the people on the escalator, so the answer for this example is $2$.

Input

The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases.

Then the descriptions of the test cases follow.

The first line of each test case contains integers: $n, m, k, H$ ($1 \le n,m \le 50$, $1 \le k,H \le 10^6$). Here, $n$ is the number of people, $m$ is the number of steps, $k$ is the height difference between neighboring steps, and $H$ is Vlad's height.

The second line contains $n$ integers: $h_1, h_2, \ldots, h_n$ ($1 \le h_i \le 10^6$). Here, $h_i$ represents the height of the $i$-th person.

Output

For each test case, output a single integer — the number of people Vlad can have a conversation with on the escalator individually.

ExampleInput

7
5 3 3 11
5 4 14 18 2
2 9 5 6
11 9
10 50 3 11
43 44 74 98 62 60 99 4 11 73
4 8 8 49
68 58 82 73
7 1 4 66
18 66 39 83 48 99 79
9 1 1 13
26 23 84 6 60 87 40 41 25
6 13 3 28
30 70 85 13 1 55

Output

2
1
4
1
0
0
3

Note

The first example is explained in the problem statement.

In the second example, Vlad can have a conversation with the person with height $11$.

In the third example, Vlad can have a conversation with people with heights: $44, 74, 98, 62$. Therefore, the answer is $4$.

In the fourth example, Vlad can have a conversation with the person with height $73$.

题目大意：
一天，Vlad好奇他在地铁的自动扶梯上能和谁进行对话。总共有n个乘客。自动扶梯总共有m个台阶，所有台阶从1到m进行编号，第i个台阶的高度为i*k。Vlad的身高是H厘米。如果两个人的身高分别为a和b，并且他们站在不同的台阶上，且他们之间的高度差等于台阶之间的高度差，那么他们可以在自动扶梯上进行对话。

例如，如果有两个人的身高分别为170和180厘米，并且m=10, k=5，那么他们可以站在编号为7和5的台阶上，其中台阶之间的高度差等于两个人之间的高度差：k*2=5*2=10=180-170。还有其他可能的方式。

给定一个大小为n的数组h，其中h_i表示第i个人的身高。Vlad想知道他可以在自动扶梯上单独和多少人进行对话。

例如，如果n=5, m=3, k=3, H=11，h=[5, 4, 14, 18, 2]，Vlad可以和身高为5的人（Vlad将站在第1个台阶上，另一个人将站在第3个台阶上）以及身高为14的人（例如，Vlad可以站在第3个台阶上，另一个人将站在第2个台阶上）进行对话。Vlad不能和身高为2的人进行对话，因为即使他们站在自动扶梯的极端台阶上，他们之间的高度差将为6，而他们之间的高度差为9。Vlad不能和自动扶梯上的其他人进行对话，所以这个例子的答案是2。

输入输出数据格式：
输入：
第一行包含一个整数t（1≤t≤1000）——测试用例的数量。
然后是t个测试用例的描述。
每个测试用例的第一行包含四个整数：n, m, k, H（1≤n,m≤50，1≤k,H≤10^6）。这里，n是人数，m是台阶数，k是相邻台阶之间的高度差，H是Vlad的身高。
第二行包含n个整数：h_1, h_2, …, h_n（1≤h_i≤10^6）。这里，h_i表示第i个人的身高。

输出：
对于每个测试用例，输出一个整数——Vlad可以在自动扶梯上单独和多少人进行对话。题目大意： 一天，Vlad好奇他在地铁的自动扶梯上能和谁进行对话。总共有n个乘客。自动扶梯总共有m个台阶，所有台阶从1到m进行编号，第i个台阶的高度为i*k。Vlad的身高是H厘米。如果两个人的身高分别为a和b，并且他们站在不同的台阶上，且他们之间的高度差等于台阶之间的高度差，那么他们可以在自动扶梯上进行对话。 例如，如果有两个人的身高分别为170和180厘米，并且m=10, k=5，那么他们可以站在编号为7和5的台阶上，其中台阶之间的高度差等于两个人之间的高度差：k*2=5*2=10=180-170。还有其他可能的方式。 给定一个大小为n的数组h，其中h_i表示第i个人的身高。Vlad想知道他可以在自动扶梯上单独和多少人进行对话。 例如，如果n=5, m=3, k=3, H=11，h=[5, 4, 14, 18, 2]，Vlad可以和身高为5的人（Vlad将站在第1个台阶上，另一个人将站在第3个台阶上）以及身高为14的人（例如，Vlad可以站在第3个台阶上，另一个人将站在第2个台阶上）进行对话。Vlad不能和身高为2的人进行对话，因为即使他们站在自动扶梯的极端台阶上，他们之间的高度差将为6，而他们之间的高度差为9。Vlad不能和自动扶梯上的其他人进行对话，所以这个例子的答案是2。 输入输出数据格式： 输入： 第一行包含一个整数t（1≤t≤1000）——测试用例的数量。 然后是t个测试用例的描述。 每个测试用例的第一行包含四个整数：n, m, k, H（1≤n,m≤50，1≤k,H≤10^6）。这里，n是人数，m是台阶数，k是相邻台阶之间的高度差，H是Vlad的身高。 第二行包含n个整数：h_1, h_2, …, h_n（1≤h_i≤10^6）。这里，h_i表示第i个人的身高。 输出： 对于每个测试用例，输出一个整数——Vlad可以在自动扶梯上单独和多少人进行对话。