Generate All Subsets Iteratively

Given a list of integers, generate its power set (i.e. all possible subsets) using an iterative (non‐recursive) method. The total number of subsets is \(2^n\), where \(n\) is the number of elements. Before generating the subsets, sort the input array in non-decreasing order. After generating all subsets, sort them first by their size and then lexicographically (i.e. compare each element in natural order for subsets of equal size).

For example, if the sorted input is [1, 2, 3], then the subsets in sorted order are:

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

</p>

inputFormat

The first line of input contains an integer \(n\) denoting the number of elements. The second line contains \(n\) space-separated integers.

outputFormat

Print each subset on a new line. For each subset, output its elements separated by a single space. If a subset is empty, output an empty line.

## sample

3
1 2 3

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

</p>