Given a positive integer $n$, print all permutations of the integers from $1$ to $n$ in lexicographical order. \InputFile One positive integer $n\:(1 \le n \le 8)$. \OutputFile Print all permutations of the integers from $1$ to $n$ in lexicographical order. Print each permutation on a separate line.