Generate All Permutations

Given a sequence of distinct integers, generate all possible permutations of the sequence. The output must list each permutation in lexicographical order, with each permutation printed on a separate line.

If the input list is empty, no output should be printed.

For example, if the input is:

3
1 2 3

then the correct 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 an integer n (n ≥ 0) representing the number of elements in the sequence. If n > 0, the second line contains n distinct integers separated by spaces.

outputFormat

Output each permutation on a new line. Within each permutation, the numbers must be separated by a single space. All permutations should be printed in lexicographical order.

3
1 2 3

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