Cho bàn cờ \(n \times n\) ô. Hãy tìm cách đặt \(n\) quân hậu vào bàn cờ sao cho không quân nào được ăn quân nào.

Yêu cầu: Tìm tất cả các phương án đặt quân hậu.

Dữ liệu vào:

Số nguyên dương \(n\ (n \leq 12)\)

Kết quả: In ra các phương án đặt theo thứ tự từ điển.

Ví dụ:

Input	Output
4	2 4 1 3 3 1 4 2

Giải thích:

Phương án 1: 2 4 1 3 nghĩa là đặt quân hậu ở cột 2 của hàng 1, cột 4 của hàng 2, cột 1 của hàng 3 và cột 3 của hàng 4