408864: GYM103366 D Character Distance

You are given an array $$$a$$$ of length $$$n$$$ and you need to rearrange the array to satisfy that there exists at least one number $$$x$$$ that appears at least once in the array and for each pair $$$i,j\ (1\le i < j\le n,a_i=a_j=x)$$$ that satisfy $$$d\le j-i$$$.

If there is no such array exist, please output $$$-1$$$. Otherwise, output the array rearranged with the minimum lexicographical order.

The first line contains one integer $$$T\ (1\le T\le 10^6)$$$, denoting the number of test cases.

Each test case contains two lines.

The first line contains two integers $$$n,d\ (1\le n,d\le 10^6)$$$ denoting the length of array $$$a$$$ and the minimum distance defined in the statement above.

The second line contains $$$n$$$ integers, the $$$i^{\text{th}}$$$ integer $$$a_i(1\le a_i\le n)$$$ denotes the $$$i^{\text{th}}$$$ number of array $$$a$$$.

It is guaranteed that the sum of $$$n$$$ in all test cases does not exceed $$$10^6$$$.

For each test case output one line.

If there is no solution output $$$-1$$$ in one line, otherwise output $$$n$$$ integers as the solution array with minimum lexicographical order.

4
4 3
1 2 1 2
4 4
1 1 2 2
6 3
3 3 2 2 1 1
7 3
1 1 2 2 2 3 3

1 2 2 1
-1
1 1 2 3 3 2
1 1 2 3 2 2 3