Hoán vị

Cho số nguyên dương \(N\).

Yêu cầu. In ra tất cả các hoán vị của các số tự nhiên từ \(1\) đến \(N\) theo thứ tự từ điển tăng dần.

Input

Gồm một dòng chứa số nguyên dương \(N\) (\(1 \le N \le 8\)).

Output

In ra tất cả các hoán vị của dãy số từ \(1\) đến \(N\).

Mỗi hoán vị in trên một dòng, các số cách nhau bởi một dấu cách.

Input

%
3

Output

%
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1