Unique Permutations

You are given a list of n integers. Your task is to generate all unique permutations of the list in lexicographical order. Note that if some numbers are repeated in the list, duplicate permutations must be eliminated.

The formula for the number of unique permutations when there are repeated elements is given by:

$$\frac{n!}{k_1!\,k_2!\,\cdots\, k_m!}$$

where \(n\) is the total number of elements and \(k_i\) is the frequency of the \(i^{th}\) distinct element.

Print each permutation on a separate line with the integers separated by a space.

inputFormat

The input is given via standard input (stdin) in the following format:

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

outputFormat

Output each unique permutation on a new line, with the numbers separated by a single space. The permutations should be listed in lexicographical order.

## sample

3
1 2 2

1 2 2
2 1 2
2 2 1

</p>