Rotating Quick Sort

You are given an array A of N integers and an integer K. Your task is to sort the array using a modified Quick Sort algorithm, called Rotating Quick Sort. In this algorithm, at each recursive call, the array is partitioned around a pivot (the middle element), and then the left partition is rotated to the right by K positions while the right partition is rotated to the left by K positions. The sorted array is then obtained by recursively sorting these rotated partitions and concatenating the results.

The rotation helper functions are defined as follows in LaTeX format:

\( \text{rotate\_right}(\text{arr}, K) = \begin{cases}\text{arr} & \text{if } |\text{arr}| = 0, \\ \text{arr}[-(K \bmod |\text{arr}|):] \;\Vert\; \text{arr}[:-(K \bmod |\text{arr}|)] & \text{otherwise.} \end{cases}\)

\( \text{rotate\_left}(\text{arr}, K) = \begin{cases}\text{arr} & \text{if } |\text{arr}| = 0, \\ \text{arr}[K \bmod |\text{arr}|:] \;\Vert\; \text{arr}[:K \bmod |\text{arr}|] & \text{otherwise.} \end{cases}\)

The overall algorithm repeatedly uses these functions during the partitioning process to eventually return the sorted array.

inputFormat

The first line of input contains an integer T representing the number of test cases. For each test case:

• The first line contains two integers N and K, where N is the number of elements in the array and K is the rotation parameter.
• The second line contains N space-separated integers representing the array A.

outputFormat

For each test case, output the sorted array in a single line with elements separated by a single space. Each test case's output should be on its own line.

## sample

1
4 0
3 1 4 2

1 2 3 4

</p>