Power Set Generation

Given a set of unique integers, your task is to generate all possible subsets (the power set) of the given set. Each subset should be printed on a new line with its elements separated by a single space. The empty subset should be printed as an empty line.

Subsets must be output in order of increasing size. For subsets with the same number of elements, they should be ordered in lexicographical order (when each subset is viewed as a sequence of integers).

The mathematical formulation is given as:

$$S = \{ A \mid A \subseteq \{a_1,a_2,\ldots,a_n\} \} $$

Note: The input is provided via standard input (stdin) and the output should be written to standard output (stdout).

inputFormat

The first line of input contains an integer n, representing the number of elements in the set. The second line contains n space‐separated integers, denoting the elements of the set. If n is 0, the second line will be empty.

outputFormat

Output all possible subsets, one per line. For each subset, print the elements in increasing order separated by a single space. For the empty subset, print an empty line. The subsets must be printed ordered first by their size (in non-decreasing order) and then lexicographically among subsets with equal size.## sample

3
1 2 3

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

</p>