All Combinations of Integers

Given an array of n integers, your task is to generate all possible combinations (subsets) of these integers. Each combination must have its elements in non-decreasing order, and the list of combinations should be sorted first by the length of the combination and then in lexicographical order.

Note that the number of subsets of an array of size n is given by \(2^n\).

Example: For the input array [1, 2, 3], the output should be:

1
2
3
1 2
1 3
2 3
1 2 3

</p>

An empty subset is represented by an empty line.

inputFormat

The first line contains an integer n representing the number of elements in the array. The second line contains n space-separated integers.

outputFormat

Output all \(2^n\) combinations, each on a separate line. For each combination, print the numbers separated by a single space. If a combination is empty, print an empty line. The combinations must be sorted first by their length (i.e. the number of elements) and then in lexicographical order.

## sample

3
1 2 3

1
2
3
1 2
1 3
2 3
1 2 3

</p>