Given an array A of size n, which is almost sorted. Each element is misplaced by no more than k positions from the correct sorted order. You need to find an efficient way to properly sort the array.

Examples:

A: [2, 4, 1, 5, 3, 7, 8, 6, 10, 9]
k: 2
Output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Testing

Input Format

The first line contains an integer ‘T’ denoting the number of test cases.

For each test case, the input contains two lines:

• Two space-separated integers ‘n’ and ‘k’.
• n space-separated integers denoting the elements of the array A.

Output format

For each test case, the output has a line with space-separated integers denoting the sorted array A.

Sample Input

2
10 2
2 4 1 5 3 7 8 6 10 9
6 1
1 4 2 5 9 7

Expected Output

1 2 3 4 5 6 7 8 9 10
1 2 4 5 7 9

Constraints

1 <= T <= 10
1 <= n <= 105
1 <= k <= 100
1 <= Ai <= 106