За заданим числом n виведіть усі перестановки чисел від 1 до n у лексикографічному порядку.

Вхідні дані

Одне число n (0 < n < 10).

Вихідні дані

Вивести усі перестановки чисел від 1 до n у лексикографічному порядку. Перестановки виводяться по одній у рядку, числа у перестановці виводяться без пропусків.