Trường THPT Chuyên Hoàng Văn Thụ - Hòa Bình

Cho trước một bàn cờ vua kích thước n x n. Hãy tìm cách đặ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ỳ vào chiếu nhau.

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

Input

• Số nguyên dương N (N <= 12)

Output

• Gồm nhiều dòng, mỗi dòng gồm N số nguyên thể hiện phương án đặt N quân cờ. Mỗi phương án ghi ra x1, x2, ..., xN; trong đó xi = j thể hiện quân cờ thứ i được đặt tại cột i và dòng j

Example

Input:
4

Output:
2 4 1 3
3 1 4 2