Unique Permutations

You are given a collection of integers that might contain duplicates. Your task is to generate all unique permutations of these integers.

For example, given the list [1, 1, 2], the unique permutations are:

• 1 1 2
• 1 2 1
• 2 1 1

The results should be printed in lexicographical order, each permutation on a separate line, with each number separated by a single space. If the input list is empty, print an empty line.

Note: In the context of this problem, lexicographical order means that permutations are compared element by element (in latex format: $[a_1,a_2,\ldots,a_n]$ is less than $[b_1,b_2,\ldots,b_n]$ if there exists an index $i$ such that $a_j=b_j$ for all $j<i$ and $a_i < b_i$).

inputFormat

The input is given via STDIN and consists of two lines:

1. The first line contains a single integer n which represents the number of elements. If n = 0, the list is empty and no further input is provided.
2. If n > 0, the second line contains n space-separated integers.

outputFormat

Print all unique permutations of the given list in lexicographical order. Each permutation should be printed on a new line with the numbers separated by a single space. For an empty list (n = 0), output an empty line.

## sample

3
1 1 2

1 1 2
1 2 1
2 1 1

</p>