Unique Subsets Generation

You are given an array of n integers (possibly containing duplicates). Your task is to generate all unique subsets of the array and print them in lexicographical order. Each subset should be formed by selecting some elements (or none) from the array and printing them with a single space as a separator. The empty subset should be printed as an empty line.

Note: The subsets must be unique even if the input array contains duplicate elements, and the output order should be the sorted order of the formatted subset strings.

The sorting order is determined by the lexicographical order of the subset when the elements are combined into a space‐separated string. For example, for the subset 1 2 and 1 2 2, the order should be: (empty), 1, 1 2, 1 2 2, etc.

Mathematically, if we denote the set of unique subsets as \( S \), then

[ S = { s \subseteq A : s \text{ is a multiset chosen from } A } ]

where \( A \) is the sorted input array. Your solution must read input from stdin and print the result to stdout.

inputFormat

The first line contains an integer n representing the size of the array. The second line contains n space-separated integers.

outputFormat

Print each unique subset in a separate line in lexicographical order. The empty subset should be printed as an empty line.

## sample

3
1 2 2

1
1 2
1 2 2
2
2 2

</p>