Power Set Generation

You are given a list of integers. Your task is to generate all possible subsets (the power set) of the given list using a backtracking approach. The subsets should be generated in the natural order of the recursion, starting from the empty subset and then adding elements in the order they appear in the input.

For example, given the list [1, 2, 3], one valid output is:

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

</p>

Note that each subset should be printed on a new line. Within each subset, the elements are separated by a single space. The empty subset is represented by an empty line.

inputFormat

The input is read from stdin. The first line contains an integer n, denoting the number of elements in the list. The second line contains n space-separated integers.

outputFormat

Output the generated subsets to stdout, one subset per line. For each subset, print its elements in the order they appear in the input, separated by a single space. If a subset is empty, print a blank line.

## sample

1
5

5

</p>