Unique Subsets

You are given a list of n integers (which may contain duplicates). Your task is to generate all possible unique subsets (the power set) of the list. Two subsets are considered unique if they differ in at least one element or in the number of occurrences of an element.

The subsets should be generated in the order they are produced by a typical backtracking algorithm: starting with the empty subset, then adding elements (skipping duplicates to avoid repetition).

Note: When printing the results, each subset should be printed on a separate line. For a non-empty subset, print the numbers separated by a single space. For the empty subset, print an empty line.

Mathematically, if the sorted input array is \(a_1, a_2, \dots, a_n\), then each subset \(S\) satisfies \(S \subseteq \{a_1, a_2, \dots, a_n\}\) and duplicates in the input are handled so that identical subsets are not output multiple times.

inputFormat

The first line contains a single integer n, representing the number of elements in the list. The second line contains n space-separated integers.

outputFormat

Output all unique subsets, one per line. For each subset, print its elements separated by a space. If a subset is empty, output an empty line.

## sample

3
1 2 2

1
1 2
1 2 2
2
2 2

</p>