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 n = sc.nextInt();
			String a = "";
			for (int i=1; i<n+1; i++) a += i;  //1からnまで入る文字列を作成
			permutation(a,"");
    	}
  }

    static void permutation( String input, String ans){
    	//1まで削ったらその回を終了して、答えを出力する
    	if (input.length() <= 1) {
    		System.out.println(ans + input);  //最後の数字はここでくっつく
    	} else {
    		for (int i=0; i<input.length(); i++) {  //inputの1、2、3…char目を分離して、残りの方に挿入する
    			permutation(input.substring(0, i) + input.substring(i + 1), ans + input.charAt(i) + " ");  //空白を入れる
    		}
    	}
    }
}

