Quốc Vương Monarch có nhiều cung tần mỹ nữ, Quốc Vương muốn phong tất cả thành nàng Hậu nhưng các vị nàng Hậu này lại luôn ganh ghét đố kỵ nhau, chính vì vậy mà Quốc Vương phải bố trí các vị nàng Hậu này sống trong những lâu đài sao cho không vị nàng Hậu nào có thể “tấn công” được vị nàng Hậu khác.
Quốc Vương có vị nàng Hậu và có lâu đài xây trên mảnh đất hình vuông (được đánh số các dòng từ , cột , mỗi ô đất có một lâu đài). Hai nàng Hậu là “tấn công” được nhau nếu hai lâu đài của hai nàng Hậu này nằm trên cùng một hàng hoặc cùng một cột hoặc cùng một đường chéo (nói nôm na thế thôi chứ quy tắc đơn giản như trong trò chơi cờ Vua vậy).
Bạn hãy tìm cách chọn lâu đài cho vị nàng Hậu này sao cho không vị nàng Hậu nào “tấn công” được nhau nhé (Quốc Vương Monarch sẽ có phần thưởng hậu hĩnh cho vị nào giúp được Quốc Vương).
Dữ liệu vào:
Một dòng duy nhất chứa số nguyên dương
Dữ liệu ra:
Dòng đầu ghi số cách chọn lâu đài cho vị hoàng Hậu
Nếu có ít nhất một phương án, dòng thứ hai ghi ra một phương án bất kỳ theo định dạng: số nguyên trong đoạn , mỗi số cách nhau bởi một dấu cách, số thứ là chỉ số dòng của lâu đài trên cột thứ .
Ví dụ:
Dữ liệu vào:
1
Dữ liệu ra:
1
1
Dữ liệu vào:
2
Dữ liệu ra:
0
Dữ liệu vào:
8
Dữ liệu ra:
92
5 7 1 3 8 6 4 2
Giải thích:
Với , có phương án, và một phương án trong số đó như hình sau:
