Sinh các hoán vị của các số tự nhiên từ 1 đến 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 1 đến n số tự nhiên đầu tiên theo thứ tự từ điển.

Lưu ý: 12 và 21 chỉ được tính là 1 hoán vị.

Input

• Số nguyên dương n (0 < n < 10).

Output

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

Example

Input:

3

Output:

1
2
3
12
13
23
123