For given an integer $n$, print all permutations of $\\{1, 2, ..., n\\}$ in lexicographic order.

Constraints

* $1 \leq n \leq 9$

Input

An integer $n$ is given in a line.

Output

Print each permutation in a line in order. Separate adjacency elements by a space character.

Examples

Input

2


Output

1 2
2 1


Input

3


Output

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
import java.util.Scanner;
class Main{
	public static void main(String[] args) {
		try(Scanner sc = new Scanner(System.in)) {
			int length = sc.nextInt();
			int[] nums = new int[length];
			for(int i = 0; i < length; i++) {
				nums[i] = i + 1;
			}
			permutation(nums, "");
		}
	}
	public static void permutation(int[] nums, String usedNums) {
		if(nums.length == 1) {
			System.out.println(usedNums + nums[0]);
		}
		else {
			for(int i = 0; i < nums.length; i++) {
				int[] pNums = new int[nums.length - 1];
				System.arraycopy(nums, 0, pNums, 0, i);
				System.arraycopy(nums, i + 1, pNums, i, nums.length - i - 1);
				permutation(pNums, usedNums + nums[i] + " ");
			}
		}
	}
}
