Bài toán đặt quân hậu

Trong một ngày nắng đẹp, FullHouse Dev đang ngồi trong phòng máy lạnh và được giao một bài toán thú vị về cờ vua. Mặc dù nhiệt độ bên ngoài đang rất cao, nhưng với không khí mát mẻ trong phòng, họ đã tập trung nghiên cứu và giải quyết bài toán đặt hậu trên bàn cờ.

Bài toán

Cho một bàn cờ có kích thước \(N \times N\), bạn cần đặt \(N\) quân hậu lên bàn cờ sao cho không có quân hậu nào có thể tấn công quân hậu khác.

INPUT FORMAT:

• Dòng duy nhất chứa một số nguyên \(N\).

OUTPUT FORMAT:

• Nếu có thể đặt được \(N\) quân hậu theo yêu cầu, in ra \(N\) dòng, mỗi dòng gồm \(N\) số nguyên. Số ở dòng thứ \(i\) và cột thứ \(j\) là 1 nếu có đặt quân hậu tại ô \((i,j)\), ngược lại là 0.
• Nếu có nhiều cách đặt, in ra một cách bất kỳ.
• Nếu không thể đặt được \(N\) quân hậu theo yêu cầu, in ra "Not possible".

Ràng buộc:

• \(1 \leq N \leq 10\)

Ví dụ

INPUT

4

OUTPUT

0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0

Giải thích

Cách đặt quân hậu trên thỏa mãn yêu cầu bài toán vì không có quân hậu nào có thể tấn công quân hậu khác theo các đường ngang, dọc hoặc chéo.