For given an integer $n$, print all permutations of $\{1, 2, ..., n\}$ in lexicographic order.
An integer $n$ is given in a line.
Print each permutation in a line in order. Separate adjacency elements by a space character.
2
1 2 2 1
3
1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1