Liệt kê hoán vị

Cho số nguyên dương \(N\). Một hoán vị của \(N\) số \(1, 2, \dots, N\) là một cách sắp xếp \(N\) số đó thành một dãy, mỗi số xuất hiện đúng một lần. Chẳng hạn các hoán vị của \(\{1, 2\}\) là \((1, 2)\) và \((2, 1)\).

Hãy in ra tất cả các hoán vị của \(1, 2, \dots, N\).

Input

Một số nguyên dương \(N\) duy nhất.

Output

Mỗi dòng in một hoán vị (các số cách nhau một dấu cách), theo thứ tự từ điển tăng dần: hoán vị nào có số ở vị trí khác nhau đầu tiên nhỏ hơn thì được in trước.

Constraints

• \(1 \le N \le 10\)

Sample Input

4

Sample Output

1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1