Unique Permutations

You are given a sequence of integers. Your task is to generate all unique permutations of these integers. The permutations should be printed in lexicographical order.

Note: The sequence may contain duplicate numbers. In such cases, you should only print distinct permutations.

For example, if the input list is [1, 1, 2], the unique permutations are:

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

inputFormat

The input is read from stdin and has the following format:

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

If n is 0, the list is considered empty.

outputFormat

Print each unique permutation on a new line to stdout. In each line, the integers in the permutation must be separated by a single space. For an empty list, output a blank line.

## sample

3
1 2 3

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

</p>