19073번 - Subsequence Sums 다국어

Yuta has a sequence of $n$ positive integers $A_1, \ldots, A_n$, and their sum is $m$. For each subsequence $S$ of $A$, he calculated the sum of elements in this subsequence.

So, now Yuta has also got $2^n$ integers between $0$ and $m$. For each $i \in [0, m]$, let $B_i$ be the number of integers $i$ he got.

Yuta shows you the array $B_i$, and he asks you to restore $A_1, \ldots, A_n$. If there are several possibilities, find the lexicographically smallest possible sequence.

The first line of the input contains two integers $n$ and $m$ ($1 \leq n \leq 50$, $1 \leq m \leq 10^4$).

The second line contains $m + 1$ integers $B_0, \ldots, B_m$ ($0 \leq B_i \leq 2^n$).

Print a single line with $n$ integers $A_1, \ldots, A_n$.

It is guaranteed that there exists at least one solution. And if there are several possible solutions, print the lexicographically smallest one.

In the first example, $A$ is $[1, 2]$. $A$ has four subsequences $[]$, $[1]$, $[2]$ and $[1,2]$, and the sums for them are $0$, $1$, $2$ and $3$. So, $B = [1, 1, 1, 1]$.