Xét dãy số nguyên ~A = (1, 2, \ldots, n)~. Hãy liệt kê tất cả các hoán vị của dãy ~A~ theo thứ tự từ điển.

Input

• Gồm một số nguyên dương ~n~ ~(n \le 10)~.

Output

• In ra ~n!~ dòng, mỗi dòng là một hoán vị, các phần tử trong hoán vị cách nhau bởi dấu cách. Các hoán vị được liệt kê theo thứ tự từ điển.

Sample Input

3

Sample Output

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