Generate Power Set

You are given an integer N and an array of N integers. Your task is to compute the power set of the given array, i.e. all possible subsets.

The output should list each subset on a new line. Each subset should be printed as space-separated integers. For the empty subset, print an empty line. The subsets must be ordered first by increasing length, and among subsets of the same length, in lexicographical order according to the original order of the elements.

For example, given the input 3 and array [1, 2, 3], the expected output is:

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

</p>

Note: The order of the elements in the input array is preserved, and subsets are sorted by their size first, then by the elements in natural order.

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 2N subsets of the array, each on a new line. Elements within a subset should be printed in the same order as they appear in the input, separated by a single space. For an empty subset, print an empty line.

## sample

3
1 2 3

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

</p>