Xét dãy số nguyên ~A=1,2,…,n~

Yêu cầu:

Hãy liệt kê tất cả hoán vị của dãy A.

Dữ liệu:

Số nguyên dương ~n≤10~.

Kết quả:

~n!~ dòng, mỗi dòng ghi một hoán vị, các phần tử trong hoán vị phải ghi cách nhau bởi dấu cách.

Input

3

Output

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