Cho trước một bàn cờ vua kích thước ~n×n~. Hãy in ra mọi phương án đặt ~n~ quân hậu sao cho vào bàn cờ sao cho không có 2 quân hậu bất kỳ nào khống chế nhau.

Ví dụ một cách đặt quân hậu trên bàn cờ 8×8

INPUT:

Đọc từ file QUEEN.INP dòng thứ nhất ghi số nguyên dương ~n≤12~

OUTPUT:

Ghi ra file QUEE.OUT gồm nhiều dòng: Mỗi dòng chứa ~n~ số ~x_1,x_2,…,x_n~ thể hiện một phương án đặt ~n~ quân hậu trên bàn cờ trong đó ~x_i=j~ tức là quân hậu được đặt tại cột ~i~ dòng ~j~.

Ví dụ:

QUEEN.INP

4

QUEEN.OUT

2 4 1 3
3 1 4 2