Cho số nguyên ~N~ (~N ≤ 10~). Hãy sinh mọi hoán vị từ 1 đến ~N~.

Dữ liệu:

Đọc từ file HOANVI.INP chứa một số nguyên dương ~N~.

Kết quả:

Ghi ra file HOANVI.OUT một tập các hoán vị được xếp theo trình tự từ điển.

Ví dụ:

HOANVI.INP

3

HOANVI.OUT

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