P4789 [BalkanOI 2018] Zalmoxis

**Translated from [BalkanOI 2018](http://boi2018.ro) Day 2 T3 “[Zalmoxis](http://boi2018.ro/assets/Tasks/BOI/Day_2/zalmoxis/zalmoxis_en.pdf)”.** **“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.

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

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

#### 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