# 53. Permutation

## I'm a slow walker, but I never walk backwards.

Write a program to output all permutations of $N$ numbers. The permutations must be outputted in sorted order according to the first number, then the second number, and so on.

## Input Format

The first line of the input gives the integer $N$ ($0 \lt N \le 9$). The second line contains $N$ numbers separated in a space to be processed. The $N$ numbers are guaranteed to be distinct.

## Output Format

The output should be consisted of $M$ lines where $M$ is the number of different permutations of the given $N$ numbers. Each line consists of $N$ numbers separated by a space representing a unique permutation. Be aware of the order of those permutations.

## Sample Input

430 10 20 40


## Sample Output

10 20 30 4010 20 40 3010 30 20 4010 30 40 2010 40 20 3010 40 30 2020 10 30 4020 10 40 3020 30 10 4020 30 40 1020 40 10 3020 40 30 1030 10 20 4030 10 40 2030 20 10 4030 20 40 1030 40 10 2030 40 20 1040 10 20 3040 10 30 2040 20 10 3040 20 30 1040 30 10 2040 30 20 10


## Hint

Suppose we have 4 numbers, 10, 20, 30, and 40. The problem of finding all the permutations of these 4 numbers can be divided into four smaller problems. The first problem is to find all the permutations of 20, 30, and 40, then place a 10 in front of each one of the permutations found. Similarly we can place a 20 in front of all permutations of 10, 30, and 40, a 30 in front of all permutations of 10, 20, and 40, and a 40 in front of all permutations of 10, 20, and 30. These are the permutations we are looking for.