Loc is researching a new sorting algorithm called Vectorized Neural-network in Ordering Integers (VNOI) - an algorithm that applies vectorized neural network technology to optimize the sorting of integer arrays. After a long period of research, Loc has finally made a new breakthrough in sorting integer arrays!
Loc has an array of ~n~ integers ~a_1, a_2, \ldots, a_n~. With the newly researched technology, Loc can perform the following operation rapidly and many times:
- Choose two indices ~i~ and ~j~ (~1 \le i, j \le n~) such that ~i + j~ is divisible by ~k~. Then swap the values of ~a_i~ and ~a_j~.
Although this is a very fast operation with the newly researched technology, Loc still wonders if it is possible to use this operation (zero or many times) to sort the array $a$ in non-decreasing order. Please help Loc check if there is any way to use the above operation to sort the array ~a~ as required!
Input
The first line contains an integer ~t~ (~1 \le t \le 10\,000~) - the number of test cases. The description of each test case is as follows.
The first line contains two integers ~n~ and ~k~ (~1 \le n \le 200\,000~, ~1 \le k \le n~) - the length of Loc's array ~a~ and the parameter ~k~ for the operation.
The second line contains ~n~ integers ~a_1, a_2, \ldots, a_n~ (~1 \le a_i \le 10^9~).
The sum of all ~n~ in all test cases is guaranteed not to exceed ~200\,000~.
Output
For each test case, print "YES" (without quotes) if there exists a sequence of operations to sort the array ~a~ in non-decreasing order. Otherwise, print "NO" (without quotes).
Scoring
Subtask | Score | Constraints |
---|---|---|
1 | 500 | ~k = 2~ |
2 | 1000 | No additional constraints |
Total | 1500 |
Sample Input 1
3
3 2
1 2 3
4 2
1 4 3 2
3 2
2 1 2
Sample Output 1
YES
YES
NO
Sample Input 2
3
3 3
1 2 3
3 3
2 1 3
3 3
3 2 1
Sample Output 2
YES
YES
NO
Sample Input 3
2
10 1
10 9 8 7 6 5 4 3 2 1
10 10
10 9 8 7 6 5 4 3 2 1
Sample Output 3
YES
NO
Notes
In the first example:
In the first test case, the array ~a~ is already sorted.
In the second test case, the array ~a = [1, 4, 3, 2]~ and ~k = 2~. We can choose indices ~i = 2~ and ~j = 4~ (since ~2 + 4 = 6~ is divisible by ~k = 2~) and swap ~a_2~ and ~a_4~ to obtain the array ~a = [1, 2, 3, 4]~.
In the third test case, the array ~a = [2, 1, 2]~ and ~k = 2~. The only valid index pair ~(i, j)~ is ~(1, 3)~, but since ~a_1 = a_3 = 2~, swapping them results in the original array. Therefore, there is no way to sort the array.
In the second example:
In the first test case, the array ~a~ is already sorted.
In the second test case, the array ~a = [2, 1, 3]~ and ~k = 3~. We can choose indices ~i = 1~ and ~j = 2~ (since ~1 + 2 = 3~ is divisible by ~k = 3~) and swap ~a_1~ and ~a_2~ to obtain ~a = [1, 2, 3]~.
In the third test case, the array ~a = [3, 2, 1]~ and ~k = 3~. The only valid index pair ~(i, j)~ is ~(1, 2)~, and swapping ~a_1~ and ~a_2~ results in the array ~a = [2, 1, 3]~. We cannot obtain any other array ~a~, so there is no way to sort the array.
Comments