Permutation Generator and Formatter

You are given a list of integers. Your task is to generate all possible permutations of this list and output each permutation as a space separated string on a new line.

The order of permutations should follow the natural order produced by the algorithm. For example, when the input is 1 2 3, one valid output is:

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

Note: The input will first contain an integer n representing the number of elements, followed by n space separated integers. Your solution should read input from standard input (stdin) and output the results to standard output (stdout).

inputFormat

The first line of input contains an integer n which specifies the number of elements in the list. The second line contains n space-separated integers.

outputFormat

Output each permutation on a new line. For each permutation, print the numbers separated by a single space. The order of the numbers in each permutation and the order of the permutations should match the natural order given by the generation algorithm.

## sample

1
1

1

</p>