Lexicographical Permutations

Given an array of integers, generate all possible permutations in lexicographical order.

The input is read from stdin and the output is written to stdout. The first line of input contains an integer n representing the number of elements in the array. The second line contains n space-separated integers. Your task is to output each permutation on a separate line with numbers separated by a single space.

The lexicographical order means that the permutations are sorted as in dictionary order (i.e. increasing order when each permutation is compared element by element).

For example, for the input:

3
1 2 3

The output should be:

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 denoting the number of elements in the array. The second line contains n space-separated integers.

outputFormat

Output all permutations of the given array in lexicographical order. Each permutation is printed on a new line with its 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

</p>