Leaking AC Unit

View as PDF

Submit solution

Points: 0.20 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

The air conditioner unit in the dorm room where Quang is staying is leaking water again. In the scorching heat of the current weather, living without an air conditioner is impossible. Therefore, while waiting for the repairman to come, he has no choice but to continue turning on the air conditioner and using his buckets to catch the water in the places where it leaks.

We can consider the background floor located right below the air conditioner as the real number line. There are ~n~ points where the water leaks from the air conditioner, and the ~i~-th leaking point has the coordinate ~x_i~. Quang has two buckets with lengths ~a~ and ~b~, respectively. For a bucket with length ~l~, if the left end of the bucket is placed at coordinate ~p~, the bucket will catch the leaking water points with coordinates from ~p~ to ~p + l~ (in this case, we say that the bucket is placed at position ~[p; p+l]~). Note that two buckets can be placed such that their intersection has a length greater than ~0~.

Help Quang check if there is a way to place his two buckets so that every leaking point is caught by at least one bucket.

Input

Each input will consist of multiple test cases. The first line of the input contains a positive integer ~t~ (~1 \le t \le 100~) — the number of test cases. The following lines describe the test cases.

The first line of each test case contains three positive integers ~n~, ~a~, ~b~ (~1 \le n \le 100~, ~1 \le a, b \le 100~) — the number of points where the air conditioner leaks water and the length of the two buckets.

The next line of each test case contains ~n~ positive integers ~x_1, x_2, \dots, x_n~ (~0 \le x_1 < x_2 < \ldots < x_n \le 100~) — the coordinates of the leaking points.

Output

For each test case, output "YES" if there is a way to place the two buckets such that every leaking point is caught by at least one bucket, or "NO" otherwise.

Scoring

The score for this problem is ~750~ points.

Sample Input 1

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

Sample Output 1

YES
YES
NO
YES

Notes

In the first example, the two buckets have lengths ~3~ and ~2~, respectively. If we place the two buckets at positions ~[1, 4]~ and ~[7, 9]~ respectively, then the leaking points at coordinates ~1~, ~2~, and ~4~ will be caught by the first bucket, and the leaking point at coordinate ~8~ will be caught by the second bucket.

In the second example, we can place the two buckets at positions ~[5, 6]~ and ~[1, 3]~, respectively, so that the leaking points at coordinates ~5~ and ~6~ will be caught by the first bucket, and the leaking points at coordinates ~1~ and ~3~ will be caught by the second bucket.

In the third example, for any bucket placement, each bucket can catch at most one leaking point, so ~2~ buckets cannot catch all ~3~ leaking points.

In the fourth example, we can place the two buckets at positions ~[0, 5]~ and ~[1, 6]~ (the intersection of the two buckets can have a length greater than ~0~).


Comments

Please read the guidelines before commenting.



  • -16
    andinhvinhthanh  commented on June 13, 2023, 2:05 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.