Mô tả

Trong toán học, một hoán vị của một tập hợp các đối tượng là sự sắp xếp các đối tượng đó theo một thứ tự nhất định. Ví dụ, với tập hợp các số {1, 2, 3}, có 6 hoán vị khác nhau là: (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), và (3, 2, 1).

Yêu cầu: Cho một số nguyên dương N, nhiệm vụ của em là viết một chương trình để liệt kê tất cả các hoán vị của các số từ 1 đến N. Các hoán vị phải được in ra theo thứ tự từ điển (lexicographical order).

Đầu vào (Input)

Một dòng duy nhất chứa một số nguyên dương N.

Ràng buộc

1 ≤ N ≤ 8

Đầu ra (Output)

In ra tất cả các hoán vị của các số từ 1 đến N. Mỗi hoán vị trên một dòng. Các số trên cùng một dòng được ngăn cách bởi một dấu cách. Các hoán vị phải được liệt kê theo thứ tự từ điển.

Testcase mẫu (Ví dụ)

Ví dụ 1:

Input

3

Output

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

Ví dụ 2:

Input

2

Output

1 2
2 1

Ví dụ 3:

Input

1

Output

1