Sinh các hoán vị từ tập \([1..n]\) biết mỗi số chỉ xuất hiện một lần và trong mỗi hoán vị số nào trong tập \([1..n]\) cũng phải xuất hiện.

Yêu cầu

• Cho số nguyên dương \(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

• 1 dòng duy nhất là số \(n\) \((0<n<10)\)

Output

• Kết quả bài toán

3

123
132
213
231
312
321