Permutation Generator

You are given a collection of n distinct integers. Your task is to generate all possible permutations of these numbers in lexicographical order.

Recall that if there are n distinct integers, the total number of permutations is given by $$ n! $$.

For example, given the input [1, 2, 3], the lexicographical order of the permutations is:

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

Please note that the input numbers may not be sorted. You must first sort them to generate the permutations in lexicographical order.

inputFormat

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

outputFormat

Output all possible permutations in lexicographical order. Each permutation should be printed on a new line with the numbers 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