เมทริกซ์ที่ดีขนาด $N$ คือเมทริกซ์ขนาด $N \times N$ ของจำนวนเต็มบวก ซึ่งผลรวม XOR ของแต่ละแถว แต่ละคอลัมน์ และเส้นทแยงมุมหลักทั้งสองเส้นมีค่าเป็น $0$

กล่าวอย่างเจาะจงคือ เมทริกซ์ $A$ ขนาด $N \times N$ จะเรียกว่าเมทริกซ์ที่ดีขนาด $N$ ถ้าสอดคล้องกับเงื่อนไขต่อไปนี้ทั้งหมด ในที่นี้ $x \oplus y$ แทนการดำเนินการ XOR แบบบิตของ $x$ และ $y$ และ $\bigoplus_{i=1}^N a_i = a_1 \oplus \dots \oplus a_N$

• $A_{i,j}$ ($1 \le i, j \le N$) เป็นจำนวนเต็มบวก
• สำหรับแต่ละ $i = 1, 2, \dots, N$, $\bigoplus_{j=1}^N A_{i,j} = 0$
• สำหรับแต่ละ $j = 1, 2, \dots, N$, $\bigoplus_{i=1}^N A_{i,j} = 0$
• $\bigoplus_{i=1}^N A_{i,i} = 0$
• $\bigoplus_{i=1}^N A_{i,N-i+1} = 0$

กำหนดจำนวนเต็มบวก $N$ มาให้

ในบรรดาเมทริกซ์ที่ดีขนาด $N$ ทั้งหมด จงแสดงเมทริกซ์หนึ่งที่มีผลรวมของสมาชิกทั้งหมด $\sum_{1 \le i, j \le N} A_{i,j}$ น้อยที่สุด

หากไม่มีเมทริกซ์ที่ดีขนาด $N$ อยู่เลย ให้รายงานว่าไม่มี

ข้อมูลนำเข้า

ข้อมูลนำเข้าประกอบด้วยจำนวนเต็ม $N$ เพียงตัวเดียว ($1 \le N \le 2 \times 10^3$)

ข้อมูลส่งออก

หากไม่มีเมทริกซ์ที่ดีขนาด $N$ ให้พิมพ์ $-1$ ในบรรทัดเดียว

หากมีอยู่ ให้พิมพ์ผลรวมของสมาชิกทั้งหมดที่น้อยที่สุดที่เป็นไปได้ในบรรทัดแรก

จากนั้นให้พิมพ์เมทริกซ์ $A$ ใน $N$ บรรทัดถัดไป โดยคั่นสมาชิกแต่ละตัวด้วยช่องว่าง กล่าวคือ บรรทัดที่ $(i+1)$ ควรประกอบด้วยสมาชิกในแถวที่ $i$ ของเมทริกซ์ $A$ คั่นด้วยช่องว่าง

หากมีคำตอบได้หลายแบบ สามารถพิมพ์คำตอบใดก็ได้

ตัวอย่าง

ข้อมูลนำเข้าตัวอย่างที่ 1

2

ข้อมูลส่งออกตัวอย่างที่ 1

4
1 1
1 1

ข้อมูลนำเข้าตัวอย่างที่ 2

1

ข้อมูลส่งออกตัวอย่างที่ 2

-1

หมายเหตุ

สำหรับตัวอย่างแรก ผลรวม XOR ของแต่ละแถว แต่ละคอลัมน์ และเส้นทแยงมุมทั้งสองเส้นเป็น $0$ ดังนั้นจึงสอดคล้องกับเงื่อนไขของเมทริกซ์ที่ดี นอกจากนี้ ในบรรดาเมทริกซ์ที่ดีขนาด $2$ ทั้งหมด ผลรวมของสมาชิกทั้งหมดไม่สามารถทำให้มีค่าน้อยกว่า $4$ ได้ ดังนั้นค่าต่ำสุดคือ $4$

สำหรับตัวอย่างที่สอง ไม่มีเมทริกซ์ที่ดีขนาด $1$ ดังนั้นจึงพิมพ์ $-1$

การดำเนินการ XOR แบบบิต $x \oplus y$ ของจำนวนเต็มไม่ลบ $x, y$ นิยามดังต่อไปนี้

• ในการเขียนแทนด้วยเลขฐานสองของ $x \oplus y$ เลขโดดในหลัก $2^k$ ($k \ge 0$) จะเป็น $1$ ก็ต่อเมื่อมีเลขโดดในหลัก $2^k$ ของการเขียนแทนด้วยเลขฐานสองของ $x$ และ $y$ เพียงตัวเดียวเท่านั้นที่เป็น $1$ มิฉะนั้นจะเป็น $0$

ตัวอย่างเช่น $3 \oplus 5 = 6$ (ในระบบเลขฐานสองคือ $011 \oplus 101 = 110$)