Permutation Generation

You are given a list of n distinct integers. Your task is to generate all possible permutations of these integers. The output must be sorted in lexicographical order.

Recall that the number of permutations is given by \( n! = 1 \times 2 \times \cdots \times n \).

For example, when the input is 3\n1 2 3, the valid output is:

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

inputFormat

The first line contains a single integer n, which is the number of elements in the array. If n > 0, the second line contains n distinct integers separated by spaces.

outputFormat

Output all permutations of the given array in lexicographical order. Each permutation should be printed on a new line with the numbers separated by a single space. If the array is empty (n = 0), output a single empty 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>