Valentine's Day

”Happy Valentine’s Day to all programming lovers!”

Little Square has received a gift for Valentine’s Day from his girlfriend, Princess Square. The gift consists of an array $a_1, ..., a_n$ of integers between $1$ and $n$. She also told Little Square that a permutation $p_1, ..., p_n$ is perfect if $p_i ≥ a_i$ for all $1 ≤ i ≤ n$. He knows that Princess Square loves the number $k$, so in order to impress her, he will do the following.

1. Write all perfect permutations of length $n$ on a paper.
2. Sort them in increasing lexicographic order. (We say that a permutation $p_1, ..., p_n$ is less than a permutation $q_1, ..., q_n$ in lexicographic order if and only if $p_1 = q_1, ...,p_{i−1} = q_{i−1}$ and $p_i < q_i$ for some $1 ≤ i ≤ n$.)
3. Select the $k$-th permutation on the list and send it back to Princess Square as a gift.

But since it is already 8 pm and Valentine’s Day ends in 4 hours, he needs to do this very fast, so he asks for your help. Write a program which, given $n, k$ and the array $a_1, ..., a_n$, finds the $k$-th perfect permutation of length $n$ in lexicographic order, and save Valentine’s Day!

Input data

The first line of input contains the integers $n$ and $k$. The second line of input contains the integers $a_1, ..., a_n$, separated by white space.

Output data

The output must contain a single line, which contains the desired permutation $p_1, ..., p_n$, separated by white space. It is guaranteed that such a permutation exists for every test case.

Restrictions

• $1 ≤ n ≤ 300 \ 000$
• $1 ≤ k ≤ 2 × 10^9$

Subtask 1 (9 points)

• $k = 1$

Subtask 2 (7 points)

• $n ≤ 9$

Subtask 3 (15 points)

• $n × k ≤ 300 \ 000$

Subtask 4 (19 points)

• $n ≤ 1 \ 000$

Subtask 5 (14 points)

• $a_1 ≥ a_2 ≥ ... ≥ a_n$

Subtask 6 (20 points)

• $n ≤ 100 \ 000$

Subtask 7 (16 points)

• No further restrictions

Examples

stdin

5 3
1 3 1 2 4

stdout

1 3 4 2 5

stdin

9 1
4 2 2 5 1 7 9 6 1

stdout

4 2 3 5 1 7 9 6 8

stdin

10 42
5 1 3 2 5 4 9 9 6 2

stdout

5 1 3 7 6 4 10 9 8 2

stdin

20 819011990
6 12 1 2 13 3 13 9 18 4 6 11 7 1 5 7 6 6 1 1

stdout

6 12 1 2 13 4 20 10 18 5 14 11 15 3 16 19 9 7 17 8

Explanations

First example: Little Square’s list is the following.

1. ⟨1, 3, 2, 4, 5⟩
2. ⟨1, 3, 2, 5, 4⟩
3. ⟨1, 3, 4, 2, 5⟩
4. ⟨1, 3, 5, 2, 4⟩
5. ⟨1, 4, 2, 3, 5⟩
6. ⟨1, 4, 3, 2, 5⟩
7. ⟨1, 5, 2, 3, 4⟩
8. ⟨1, 5, 3, 2, 4⟩
9. ⟨2, 3, 1, 4, 5⟩
10. ⟨2, 3, 1, 5, 4⟩
11. ⟨2, 4, 1, 3, 5⟩
12. ⟨2, 5, 1, 3, 4⟩
13. ⟨3, 4, 1, 2, 5⟩
14. ⟨3, 5, 1, 2, 4⟩
15. ⟨4, 3, 1, 2, 5⟩
16. ⟨5, 3, 1, 2, 4⟩
    Thus we select the 3rd one i.e. $⟨1, 3, 4, 2, 5⟩$.

Second example: The first few permutations in Little Square’s list are the following.

1. ⟨4, 2, 3, 5, 1, 7, 9, 6, 8⟩
2. ⟨4, 2, 3, 5, 1, 7, 9, 8, 6⟩
3. ⟨4, 2, 3, 5, 1, 8, 9, 6, 7⟩
4. ⟨4, 2, 3, 5, 1, 8, 9, 7, 6⟩
5. ⟨4, 2, 3, 5, 6, 7, 9, 8, 1⟩
6. ⟨4, 2, 3, 5, 6, 8, 9, 7, 1⟩
7. ⟨4, 2, 3, 5, 7, 8, 9, 6, 1⟩
8. ⟨4, 2, 3, 5, 8, 7, 9, 6, 1⟩
9. ⟨4, 2, 3, 6, 1, 7, 9, 8, 5⟩
10. ⟨4, 2, 3, 6, 1, 8, 9, 7, 5⟩
    Thus we select the first one i.e. $⟨4, 2, 3, 5, 1, 7, 9, 6, 8⟩$.