Trong các bài toán tối ưu hóa, tìm kiếm lời giải và lập lịch công việc, việc duyệt qua mọi khả năng xảy ra của một cấu hình là vô cùng quan trọng. Cho một tập hợp gồm \(N\) số nguyên phân biệt từ \(1\) đến \(N\). Bạn được yêu cầu lập trình liệt kê tất cả các hoán vị khác nhau của tập hợp này theo thứ tự từ điển tăng dần bằng thuật toán đệ quy quay lui (backtracking). Đây là bài toán cơ sở giúp bạn làm quen với cách xây dựng không gian trạng thái và kỹ thuật quay lui phổ biến trong các kỳ thi chọn học sinh giỏi Tin học các cấp.

Định dạng đầu vào

• Một dòng chứa số nguyên dương \(N\) (\(1 \le N \le 8\)).

Định dạng đầu ra

• Liệt kê mỗi hoán vị trên một dòng, các phần tử cách nhau bởi dấu cách.

Ví dụ

Input:

3

Output:

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