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

Входные данные

Одно натуральное число n (1 ≤ n ≤ 8).

Выходные данные

Вывести все перестановки из чисел от 1 до n в лексикографическом порядке. Каждую перестановку следует выводить в отдельной строке.