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