ZalSequence Insertion

Translated from BalkanOI 2018 Day2 T3 "Zalmoxis".

A ZalPunch is an operation on a sequence that, in one move, takes any positive integer x in the sequence and replaces it in‐place with two copies of x−1. For example:

• Correct: [1, 1] ⟶ [0, 0, 1] (the first 1 was punched).
• Correct: [1, 23, 3] ⟶ [1, 22, 22, 3] (the 23 was punched).
• Incorrect: [1, 3] ⟶ [2, 1, 2] (the first 2 is not in the punched position).

Starting from the sequence [30], applying any number (possibly zero) of ZalPunch operations produces what is called a ZalSequence (note that [30] is itself a ZalSequence).

You are given a sequence S with N numbers. By inserting exactly K additional numbers (at arbitrary positions, i.e. not by performing K ZalPunch operations) into S, transform it into a ZalSequence. It is guaranteed that a solution exists.

Note on the structure of a ZalSequence:

A sequence T is a ZalSequence if and only if by repeatedly performing the following merge operation on adjacent equal numbers you eventually obtain a single number 30. The merge operation is the reverse of the ZalPunch: if two consecutive numbers x appear, they can be merged into a single x+1, all while preserving order. For example, [1,1] merges to [2].

inputFormat

The first line contains two integers N and K (1 ≤ N, K, and N+K is such that a solution exists).

The second line contains N integers S[1], S[2], …, S[N] — the given sequence.

outputFormat

Output the resulting ZalSequence (a sequence of N+K numbers) in one line separated by spaces. The output sequence must contain S as a subsequence (in the same order as in S) and must be a valid ZalSequence (i.e. it can be merged by repeatedly replacing two adjacent equal numbers x by x+1 until a single number remains, which must equal 30).

sample

1 0
30

30