Problem Description

Translated from BalkanOI 2018 Day2 T3 "Zalmoxis"

"ZalPunch" is a method to modify a sequence, where each ZalPunch can replace any positive integer $x$ in the sequence with two $(x-1)$ in-place.
Correct example: $[1, 1] \xrightarrow{ZalPunch} [0, 0, 1]$;
Correct example: $[1, 23, 3] \xrightarrow{ZalPunch} [1, 22, 22, 3]$;
* Incorrect example: $[1, 3] \xrightarrow{ZalPunch} [2, 1, 2]$ (the first 2 is not in its original position).

Starting from the sequence $[30]$, any sequence obtained by modifying it with ZalPunch any number of times is called a "ZalSequence" (including the sequence $[30]$).
Given a sequence $S$ with $N$ elements, insert $K$ numbers into it (not using $K$ ZalPunches) to make it a ZalSequence. A solution is guaranteed to exist.

Input Format

The first line contains two integers $N, K$.
The second line contains $N$ integers representing the sequence $S$.

Output Format

Output $N+K$ integers representing the new sequence.

Sample Input and Output

Sample Input #1

5 1
29 27 25 25 28

Sample Output #1

29 27 25 25 26 28

Sample Input #2

1 5
29

Sample Output #2

29 28 27 26 25 25

Notes

Sample Explanation 1

$[30] \rightarrow [29, 29] \rightarrow [29, 28, 28] \rightarrow [29, 27, 27, 28] \rightarrow [29, 27, 26, 26, 28] \rightarrow [29, 27, 25, 25, 26, 28]$

Sample Explanation 2

$[30] \rightarrow [29, 29] \rightarrow [29, 28, 28] \rightarrow [29, 28, 27, 27] \rightarrow [29, 28, 27, 26, 26] \rightarrow [29, 28, 27, 26, 25, 25]$

For $30\%$ of the test cases, $K=1$.
For all test cases, $1 \leq N, K \leq 10^6$, $1 \leq N + K \leq 10^6$.

见题面 Input 部分

见题面 Output 部分