Competitions

# Permutations

Given a positive integer n, print all permutations of the integers from 1 to n in lexicographical order.

#### Input

One positive integer n (1n8).

#### Output

Print all permutations of the integers from 1 to n in lexicographical order. Print each permutation on a separate line.

Time limit 1 second
Memory limit 128 MiB
Input example #1
3
Output example #1
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1