Cho tập hợp A gồm \(n\) phần tử \((n \ge 1)\). Mỗi kết quả của sự sắp xếp thứ tự \(n\) phần tử của tập hợp A được gọi là một hoán vị của \(n\) phần tử đó. Ví dụ, với tập hợp gồm các số \(A = (1,2,3,4,5,6)\), mỗi cách sắp thứ tự sẽ tạo thành một dãy các số không lặp lại như sau: \((1, 2, 3, 4, 5, 6)\) hoặc \((3, 4, 6, 1, 2, 5)\) hay \((2, 1, 4, 6, 5, 3)\). Các cách sắp xếp như vậy được gọi là một hoán vị của A.

Yêu cầu:

Hãy liệt kê ra các hoán vị của \(A = {1,2,...,n}\) theo thứ tự từ điển tăng dần.

Input Specification

• Gồm 1 dòng là số nguyên \(n\) \((0<n \le 9)\).

Output Specification

• Tất cả các hoán vị của A theo thứ tự từ điển, mỗi dãy trên một dòng.

Sample Input

    3

Sample Output

    123
    132
    213
    231
    312
    321