Permutation Generation

You are given an integer \( n \) and your task is to generate all possible permutations of the numbers \( 1, 2, \dots, n \). Each permutation should be printed on a separate line, and the numbers in each permutation should be separated by a single space.

Note: \( n \) will be a positive integer, and you can assume \( 1 \le n \le 8 \) for computational feasibility.

For example, if \( n = 3 \), the output should be:

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

inputFormat

The input is given via standard input (stdin) and consists of a single integer \( n \) on one line, where \( n \) represents the number of elements to permute.

Example:

3

outputFormat

Output the list of all permutations of the numbers from 1 to \( n \) to standard output (stdout). Each permutation must be on its own line with numbers separated by spaces.

Example (for \( n = 3 \)):

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

## sample

1

1

</p>