Unique Permutations Generation

You are given a list of n integers. Your task is to generate all unique permutations of these numbers. Two permutations are considered different if there exists an index i such that the i^th elements differ.

The mathematical number of unique permutations for a list can be described by the formula \[ P = \frac{n!}{\prod_{i} {c_i}! \] where c_i represents the count of each distinct number in the list.

Output the unique permutations in lexicographical order, each permutation on a new line with its numbers separated by a space.

inputFormat

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

outputFormat

Output all unique permutations in lexicographical order. Each permutation should be printed on its own line with each integer separated by a single space.

## sample

3
1 2 3

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

</p>