Cho trước số nguyên dương \(n\). Viết chương trình in ra các hoán vị của bộ \(n\) số nguyên dương đầu tiên, theo thứ tự từ điển.

Input Specification

Gồm số nguyên dương \(n\) được ghi trên một dòng duy nhất.

Output Specification

In ra kết quả mỗi hoán vị trên một dòng.

Constraints

\(n \leq 9\)

Input Sample

3

Output Sample

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