Zalmoxis

Time limit1sMemory limit512 MB

Summary

Insert K values into S to form a ZalSequence of length N+K, where each value v is a leaf at depth 30-v of a binary split tree.

Level: Medium7 of 10
Topics: Math, Greedy, Implementation
Solved: No attempts yet

Problem

Tanaka has become interested in Dacian mythology (the Dacians lived in the area of Romania before the Romans). In this mythology, Zalmoxis was the supreme god, and Pleistoros was the god of war. In Tanaka's new interpretation, Zalmoxis has a new powerful attack, the ZalPunch, and he loves ZalSequences.

The ZalPunch is an attack that can be applied to non-negative integer sequences. It takes a strictly positive integer $x$ from the sequence and replaces it with two occurrences of $x-1$ . For example:

[1] becomes [0, 0]
[1, 23, 3] becomes [1, 22, 22, 3]
But [1, 3] does not become [2, 1, 2], since the order of the sequence matters.

ZalSequences are the sequences that Zalmoxis loves. A sequence is a ZalSequence if it is one of the following:

The sequence [30].
A sequence that can be obtained by applying a ZalPunch to another ZalSequence.

For example, [30], [29, 29], and [29, 28, 27, 27] are ZalSequences, but [28, 29, 28] is not.

To begin with, Zalmoxis creates a ZalSequence of length $N + K$ . However, one of his enemies destroys $K$ of the values in this sequence, leaving $N$ remaining values. Call this sequence $S$ . Given $N$ , $K$ , and $S$ , insert $K$ values into $S$ to create any ZalSequence of length $N + K$ . It is guaranteed that this is possible in all test cases.

Input

The first line contains the positive integers $N$ and $K$ .

The next line contains $N$ non-negative integers, the values of $S$ .

Output

The only line of output contains a sequence of $N + K$ non-negative integers that is a ZalSequence and contains $S$ as a subsequence. The elements of $S$ appear at possibly non-consecutive positions in the output.

Constraints

$1 \le N \le 1{,}000{,}000$
$1 \le K \le 1{,}000{,}000$
$1 \le N + K \le 1{,}000{,}000$
The sequence in the input is a subsequence of a ZalSequence of length $N + K$ .

Hints

In the first example, [29, 27, 25, 25, 26, 28] can be obtained from [30] by the following ZalPunches:

[30] → [29, 29] → [29, 28, 28] → [29, 27, 27, 28] → [29, 27, 26, 26, 28] → [29, 27, 25, 25, 26, 28]

In the second example, [29, 28, 27, 26, 25, 25] can be obtained from [30] by the following ZalPunches:

[30] → [29, 29] → [29, 28, 28] → [29, 28, 27, 27] → [29, 28, 27, 26, 26] → [29, 28, 27, 26, 25, 25]

Examples2

Example 1
Input
```
5 1
29 27 25 25 28
```
Expected output
```
29 27 25 25 26 28
```
Example 2
Input
```
1 5
29
```
Expected output
```
29 28 27 26 25 25
```