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\}.