Sinh các hoán vị của các số tự nhiên từ \(1\) đến \(n\).

Yêu cầu: Cho \(n\) hãy in tất cả các hoán vị của \(n\) số tự nhiên đầu tiên theo thứ tự từ điển.

Input

• Số nguyên dương \(n (n \leq 9)\).

Output

• Tất cả các hoán vị của \(n\) số tự nhiên đầu tiên theo thứ tự từ điển.

Example

3 

123
132
213
231
312
321