# Non-Decreasing Subsequence of size K solution codechef

You are given a positive integer KK and an array AA consisting of NN non-negative integers. Find the lexicographically smallest sequence BB that satisfies the following conditions

• We can obtain BB by rearranging the elements in AA.
• The length of longest non-decreasing subsequence of BB is equal to KK.

If no such sequence exists, print 1−1.

### Non-Decreasing Subsequence of size K solution codechef – Input Format

• First line of the input contains TT, the number of testcases. Then the testcases follow.
• First line of each test case contains two space separated integers NN and KK.
• Second line of each test case contains NN space separated integers describing the array AA.

### Output Format

For each test case, output the array BB in a single line with a space between two consecutive elements. And output 1−1 if no such array BB exists.

### Constraints

• 1T2001≤T≤200
• 1N2001≤N≤200
• 1KN1≤K≤N
• 1AiN1≤Ai≤N
• Sum of NN over all test cases doesn’t exceed 200200.

### Non-Decreasing Subsequence of size K solution codechef

4
3 1
2 1 3
3 2
2 1 3
3 3
2 1 3
3 1
2 2 3


### Sample Output 1

3 2 1
1 3 2
1 2 3
-1


### Explanation

There are 66 arrays that are rearrangements of the array [2,1,3][2,1,3].

• [1,2,3][1,2,3] with length of longest non-decreasing subsequence equal to 33.
• [1,3,2][1,3,2] with length of longest non-decreasing subsequence equal to 22.
• [2,1,3][2,1,3] with length of longest non-decreasing subsequence equal to 22.
• [2,3,1][2,3,1] with length of longest non-decreasing subsequence equal to 22.
• [3,1,2][3,1,2] with length of longest non-decreasing subsequence equal to 22.
• [3,2,1][3,2,1] with length of longest non-decreasing subsequence equal to 11.

Test case 1: Non-Decreasing Subsequence of size K solution codechef

Observe from the list above that [3,2,1][3,2,1] is the only rearrangement of [2,1,3][2,1,3] with the length of the longest non-decreasing subsequence equal to 33. And hence [3,2,1][3,2,1] is the lexicographically smallest that satisfies the given conditions.

Test case 2: Non-Decreasing Subsequence of size K solution codechef

Observe from the above list the [1,3,2][1,3,2] is the lexicographically smallest among all those rearrangements with the length of the longest non-decreasing subsequence equal to 22. And hence [1,3,2][1,3,2] is the lexicographically smallest that satisfies the given conditions.

Test case 3:

Observe from the list above that [1,2,3][1,2,3] is the only rearrangement of [2,1,3][2,1,3] with the length of the longest non-decreasing subsequence equal to 11. And hence [1,2,3][1,2,3] is the lexicographically smallest that satisfies the given conditions.

Test case 4: Non-Decreasing Subsequence of size K solution codechef

There are only 33 possible ways to rearrange [2,2,3][2,2,3].

• [2,2,3][2,2,3] with length of longest non-decreasing subsequence equal to 33.
• [2,3,2][2,3,2] with length of longest non-decreasing subsequence equal to 22.
• [3,2,2][3,2,2] with length of longest non-decreasing subsequence equal to 22.

So there does not exist any rearrangement of [2,2,3][2,2,3] with the length of the longest non-decreasing subsequence equal to 11.