Cho tập hợp ~A = {1, 2, …, n}~. Liệt kê các hoán vị của ~A~.

Input

• Một dòng duy nhất chứa số nguyên dương ~n~

Giới hạn:

• ~1 ≤ n ≤ 9~.

Output

• Gồm nhiều dòng, mỗi dòng là một hoán vị của tập ~A~, các hoán vị liệt kê theo thứ tự từ điển tăng dần, mỗi số trên một dòng cách nhau bởi một dấu cách

Lưu ý:

• Không in ra khoảng trắng thừa

Sample

Input #1

3

Output #1

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

Hint

Trong #1, tập ~A~ có ~3~ phần tử thì sẽ có ~6~ hoán vị, các hoán vị được liệt kê theo thứ tự tăng dần như trên.

Problem source: Chuyên Sơn La Online Judge