Preparing NOJ # Character Distance

2000ms 262144K

## Description:

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.

## Input:

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$.

## Output:

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.

## Sample Input:

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


## Sample Output:

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


Info Provider CodeForces Gym

Code GYM103366D

Tags

Submitted 0

Passed 0

AC Rate 0%

Date 10/25/2021 22:31:51

Related

Nothing Yet