Sort A “K” Sorted Doubly Linked List

You’re given a doubly-linked list with N nodes, where each node deviates at max K position from its position in the sorted list. Your task is to sort this given doubly linked list.

For example :

Let us consider K is 3, an element at position 4 in the sorted doubly linked list, can be at positions 1, 2, 3, 4, 5, 6, 7 in the given linked list because the absolute difference of all these indices with 4 is at most 3.

Note :

All elements are distinct.

A doubly linked list is a type of linked list that is bidirectional, that is, it can be traversed in both directions, forward and backward. 

Input Format :

The first line of input contains T, the number of test cases.

The first line of each test case contains an integer K, as specified in the problem statement.

The second line contains the elements of the doubly linked list separated by a single space and terminated by -1. Hence, -1 would never be a list element.

Output Format :

For each test case print in a new line the sorted linked list, the elements of the sorted list should be single-space separated, terminated by -1.  

Note :

You don’t need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= N <= 10000
1 <= K < N

Time Limit: 1 sec

Sample Input 1 :

1
4 
6 5 3 2 8 10 9 -1

Sample Output 1 :

2 3 5 6 8 9 10 -1

Explanation For Sample Input 1 :

We could move 6 from position 1 to as far as position 5(as K=4) and we moved it to position 4 and it can be seen that after that all elements to the left(i.e position 1 to 3) are less than 6, hence 10 is at its best position now. Similarly, we do this for all the elements, to reach our answer. 

Sample Input 2 :

1
4
10 9 8 7 4 70 60 50 -1

Sample Output 2 :

4 7 8 9 10 50 60 70 -1