eolymp
bolt
Try our new interface for solving problems
Problems

All permutations of given length

All permutations of given length

Time limit 1 second
Memory limit 128 MiB

Given number n. Print all permutations of numbers from 1 to n in lexicographical order.

Input data

One number n (0 < n < 10).

Output data

Print all permutations of numbers from 1 to n in lexicographical order. Print each permutation in a separate line. Do not print spaces between numbers in one line.

Examples

Input example #1
3
Output example #1
123
132
213
231
312
321