Given an integer n, arrange the numbers 1~n in a row, which can yield many different permutations.

Now, please output all permutations in reverse lexicographical order.

Input format
One line containing an integer n.

Output format
Output all permutation schemes in lexicographical order, each scheme on a separate line.

Data range
1 ≤ n ≤ 7

Sample input

3

Sample output

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