N Quân Hậu

Trong một buổi ăn tối, FullHouse Dev được đưa ra một bài toán thú vị về cờ vua. Họ được yêu cầu phải tìm cách đặt các quân hậu trên bàn cờ sao cho không quân hậu nào có thể tấn công quân hậu khác. Với tinh thần háo hức, FullHouse Dev đã bắt đầu phân tích và giải quyết bài toán này.

Bài toán

Cho một bàn cờ có kích thước \(N \times N\), nhiệm vụ của bạn là đặ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\) - kích thước của bàn cờ và số lượng quân hậu cần đặt.

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ó quân hậu được đặt tại ô \((i,j)\), ngược lại là 0.
• Nếu có nhiều cách đặt quân hậu, chỉ cần 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" (không có dấu ngoặc kép).

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

Trong ví dụ này, các quân hậu được đặt tại các vị trí (1,2), (2,4), (3,1), và (4,3). Với cách đặt này, không có quân hậu nào có thể tấn công quân hậu khác theo luật cờ vua.