Cops and the Thief Devu

Link here.

There are 100 houses located on a straight line. The first house is numbered 1 and the last one is numbered 100. Some M houses out of these 100 are occupied by cops.

Thief Devu has just stolen PeePee's bag and is looking for a house to hide in.

PeePee uses fast 4G Internet and sends the message to all the cops that a thief named Devu has just stolen her bag and ran into some house.

Devu knows that the cops run at a maximum speed of x houses per minute in a straight line and they will search for a maximum of y minutes. Devu wants to know how many houses are safe for him to escape from the cops. Help him in getting this information.

Input

First line contains T, the number of test cases to follow.

First line of each test case contains 3 space separated integers: M, x and y.

For each test case, the second line contains M space separated integers which represent the house numbers where the cops are residing.

Output

For each test case, output a single line containing the number of houses which are safe to hide from cops.

Constraints

• 1 ≤ T ≤ 10⁴
• 1 ≤ x, y, M ≤ 10

Example

Input:
3
4 7 8
12 52 56 8
2 10 2
21 75
2 5 8
10 51

Output:
0
18
9

Explanation

Example 1 : Cops in house 12 can cover houses 1 to 68, and cops in house 52 can cover the rest of the houses. So, there is no safe house.

Example 2 : Cops in house 21 can cover houses 1 to 41, and cops in house 75 can cover houses 55 to 95, leaving houses numbered 42 to 54, and 96 to 100 safe. So, in total 18 houses are safe.

Problem Solving

• First thing to notice is that it's a range problem. Given a range 1-100 we have to subtract ranges.
• Simple math tells us that for every Mi range for that cop is i +- x * y. Current position + (speed * time) (distance) the cop can cover.
• Now we have 1-100 range and have to subtract all Mi ranges and leftover will be our answer. 
• We need to calculate the total sum of ranges, excluding the overlaps and finally subtract the the total from 100, to get safe houses. 
• I mistakenly read the problem to output the indexes of houses, however now thinking about it that would have been a different problem.
• We can create a list of ranges and while adding a range to list merge the range if required to make a bigger range. Finally we can compute the total sum of the ranges in the list and subtract that from 100. 
• Here to make a list we can use std::vector, to represent a range we can use std::pair 
• Also while merging we need to search through all merges possible therefore if we can maintain a sorted list then the while merging we only have to check the last element. 
• Therefore we have to sort the houses list first and then give it to adding range. 
•  The submission went successful here.

Learning 

• I have a feeling that we can still improve this complexity of mlogm, if we would know how to store ranges properly. 
• May be in future we can study such  data structures. 
• We also used a built in sorting function which currently we have not implemented, so going forward we need to learn about sorting. 
• Since in the certification course all sample problems are done, I would pick up problems from "Elements of Programming Interview" to cover more array and vector problems.