Problem Description

Translated from BalkanOI 2018 Day 2 T3 “Zalmoxis”.

“ZalPunch” is a way to modify a sequence. Each time you perform a ZalPunch, you can take any non-negative integer $x$ in the sequence and replace it in place with two $(x-1)$.

• Correct example: $[1, 1]\xrightarrow{ZalPunch}[0, 0, 1]$;
• Correct example: $[1,23,3]\xrightarrow{ZalPunch}[1,22,22,3]$;
• Wrong example: $[1,3]\xrightarrow{ZalPunch}[2,1,2]$ (the first $2$ is not in the original position).

Starting from the sequence $[30]$, all sequences that can be obtained by applying ZalPunch any number of times are called “ZalSequence” (including $[30]$).
You are given a sequence $S$ with $N$ elements. Insert $K$ numbers into it (not performing ZalPunch $K$ times) so that it becomes a ZalSequence. It is guaranteed that a solution exists.

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.

5 1
29 27 25 25 28

29 27 25 25 26 28

1 5
29

29 28 27 26 25 25

Hint

Sample Explanation 1

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

Sample Explanation 2

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

For $30\%$ of the testdata, $K=1$.
For all testdata, $1 ≤ N,K ≤ 10^6,$ $1 ≤ N + K ≤ 10^6$.

Thanks to Planet6174 for providing the translation.

Thanks to @tiger2005 for providing the SPJ.

Translated by ChatGPT 5