题目描述

翻译自 BalkanOI 2018 Day2 T3「Zalmoxis」

ZalPunch 是一种修改数列的方式，每次 ZalPunch 可以将数列中的任意一个正整数 $x$ 原地替换成两个 $(x-1)$。

• 正确示范：$[1, 1]\xrightarrow{ZalPunch}[0, 0, 1]$；
• 正确示范：$[1,23,3]\xrightarrow{ZalPunch}[1,22,22,3]$；
• 错误示范：$[1,3]\xrightarrow{ZalPunch}[2,1,2]$（第一个 2 不在原位）。

从数列 $[30]$ 开始，用 ZalPunch 修改该数列任意多次，所得到的所有数列都称为 ZalSequence（含数列 $[30]$）。
给你一个有 $N$ 项的数列 $S$，请在其中插入 $K$ 个数（不是使用 $K$ 次 ZalPunch），使之变成 ZalSequence。保证有解。

输入格式

第一行有两个整数 $N, K$。
第二行有 $N$ 个整数，表示数列 $S$。

输出格式

输出 $N+K$ 个整数，表示新数列。

样例 1

input

5 1
29 27 25 25 28

output

29 27 25 25 26 28

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

样例 2

input

1 5
29

output

29 28 27 26 25 25

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

数据范围与提示

对于 $30\%$ 的数据，$K=1$。
对于所有数据，$1 ≤ N,K ≤ 10^6, $ $1 ≤ N + K ≤ 10^6$。