After an epic heist crew recruitment montage, a group of aliens is preparing to steal all the cows on Earth! There are $n$ cow farms on Earth and the $i$-th farm has $c_i$ cows. The team needs to move swiftly, so they need to fine tune their ship's tractor beams. The ship has $30$ tractor beams and the $i$-th tractor beam can be tuned to pull in exactly $X_i$ cows. As a member of the crew your task is to tune the tractor beams in such a way that you can steal all the cows from any of the farms in a single pull.

Formally, for each $i$ in $1,2,\dots,n$, there should be a subset of the tractor beams that can pull in exactly $c_i$ cows. If there are multiple answers, print any.

Input

The first line contains a single integer $n$.

The next line contains $n$ integers $c_1,\,c_2,\cdots,\,c_n$.

Output

Print $30$ integers $X_1\ X_2 \dots\ X_{30}$ in a line.

Constraints

• $1 \leq n \leq 10^5$
• $1 \leq c_i \leq 10^6$
• $0 \leq X_i \leq 10^6$

Example 1

Input:

3
4 5 6

Output:

4 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Explanation:
The sets of beams that can be used to pull in the cows are: $\{1\}$ for farm $1$, $\{1,\,2\}$ for farm $2$ and $\{1,\,3\}$ for farm $3$.

Example 2

Input:

6
4 2 3 10 7 1

Output:

 1 2 5 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Explanation:
The sets are $\{2,\,4\}$, $\{2\}$, $\{1,\,2\}$, $\{1,\,2,\,3,\,4\}$, $\{2,\,3\}$ and $\{1\}$.