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\) chữ cái đầ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

abc
acb
bac
bca
cab
cba