Find all permutation of the set $S=\\{1,2,...,n\\}$.
### Input
- A single line contains an integer $n$.
### Output
- Print all permutations of $S$, in lexicographic order.
### Constraints
- $1 \le n \le 9$.
### Example
Input:
```
3
```
Output:
```
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
```
