Description

There are $N$ cards stacked together. On the $i$-th card, there is a number $a_i$, meaning that at least $a_i$ cards below it have incorrect information. If there are indeed at least $a_i$ cards below it with incorrect information, then the information on this card is correct; otherwise, the information on this card is incorrect. (We consider that below the bottom card there are $0$ incorrect cards.)

Now you need to rearrange the order of the cards so that exactly $K$ cards have incorrect information.

Input Format

The first line contains two positive integers $N$ and $K$ $(1 \le N \le 5 \times 10^5, 0 \le K \le N)$, representing the number of cards and the required number of incorrect pieces of information.

The next $N$ lines each contain one number, representing the corresponding $a_i$ $(0 \le a_i \le 5 \times 10^5)$.

Output Format

If no rearrangement exists, output $-1$. Otherwise, output the $a_i$ of the $N$ cards from top to bottom. If there are multiple solutions, output any one.

4 2
1 2 2 3

2 3 1 2

5 3
2 1 3 0 3

3 3 0 1 2

6 4
0 2 5 2 0 1

-1

Hint

For $30\%$ of the testdata, $N \le 16$.

For another $40\%$ of the testdata, $N \le 2000$.

Explanation of Sample 2:

The $5$-th card shows $2$, but there are only $0$ incorrect cards below it, so it is incorrect.

The $4$-th card shows $1$. There is $1$ incorrect card below it (the $5$-th), so it is correct.

The $3$-th card shows $0$. There is $1$ incorrect card below it (the $5$-th), so it is correct.

The $2$-th card shows $3$, but there is only $1$ incorrect card below it (the $5$-th), so it is incorrect.

The $1$-st card shows $3$, but there are only $2$ incorrect cards below it (the $5$-th and the $2$-nd), so it is incorrect.

Therefore, there are $3$ incorrect cards in total.

Translated by ChatGPT 5