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. Lần này để hiểu sâu hơn về cách liệt kê hoán vị, Mr Toàn muốn bạn in ra hoán vị lớn nhất trước rồi tiếp đến các hoán vị nhỏ hơn.

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 giảm 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, giữa các phần tử có một dấu cách trống.

Sample Input

    3

Sample Output

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