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

Вхідні дані

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

Вихідні дані

Вивести усі перестановки з цілих чисел від 1 до n у лексикографічному порядку. Кожну перестановку слід виводити в окремому рядку.