Liệt kê tất cả các hoán vị của các số ~ 1, 2,…,n ~ theo thứ tự từ điển.

Dữ liệu vào:

Số nguyên dương ~ n ~ ~ (1≤n≤10) ~

Kết quả:

Ghi các hoán vị tìm được theo thứ tự từ điển, mỗi hoán vị in trên 1 dòng

Ví dụ:

Input

3 

Output

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