A - Aprendiendo a permutar

Time limit: 3 seconds
Memory limit: 256 megabytes
Languages: MS C# .NET 4.7.2053,GNU G++11 5.1.0 ...

Fito aprendió hoy sobre permutaciones, pero como buen amante de la computación, él desea algo más que $n!$. Fito quiere imprimir todas las permutaciones de $n$ elementos. Para ello, él te pide que hagas un programa para verificar el suyo: Dado un entero $n$, listar todas las permutaciones de los números $1, 2, ..., n$ en orden lexicográfico.

Input

Línea 1: Un entero $n$ $(1 \leq n \leq 9)$.

Output

Línea 1 ... n!: La $i$-ésima línea contendrá la $i$-ésima permutación, $n$ números separados por espacio.

Sample test(s)

Input
3
Output
1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1