Sorting an array is not any easy task. You have to apply so many difficult algorithms to perform the sorting. In this task you are going to follow a new technique to sort an array invented by our NSUPS algorithms specialists.
You'll be given an array A of N integers and two more integers X and K. You are allowed to perform the following operation to change the array elements:
Select any integer from the array and increment its value by X.
You have to find out whether you can make the array sorted after performing the above operation maximum K times.
Input
The first line of the input contains an integer T which denotes the number of test cases.
The first line of each test case contains three integers N, K and X. The following two lines of a test case represent the elements of the array A.
Constraints
- 1 ≤ T ≤ 20
- 1 ≤ N ≤ 50000
- 1 ≤ K ≤ 1000000000
- 1 ≤ X, Ai ≤ 100000
Output
For each test case, print the result in the format “Case X: Y” where Y is either YES or NO depending on the result.
Sample
| Input | Output |
|---|---|
2 5 8 3 7 5 3 2 1 5 11 3 7 5 3 2 1 | Case 1: NO Case 2: YES |
