 ## Innovative Sorting

View as PDF

Points: 0.40 (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

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).

1 500 ~k = 2~
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.