Hoán vị

Cho số nguyên \(n\) \((1 \le n \le 8)\). Hãy in ra tất cả hoán vị của các số từ \(1\) đến \(n\), theo thứ tự từ điển tăng dần.

Input

Một dòng duy nhất chứa số nguyên \(n\).

Output

Ghi ra tất cả hoán vị của dãy số \(1, 2, \ldots, n\), mỗi hoán vị trên một dòng, theo thứ tự từ điển tăng.
Các số trong một hoán vị cách nhau bởi đúng một dấu cách.

Sample Input 1

3

Sample Output 1

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