Cho bàn cờ vua có $n×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 ≤ 12)$

Kết quả

• In ra các phương án đặt theo thứ tự từ điển.

Ví dụ:

Input 1

4 

Output 1

2 4 1 3 
3 1 4 2