מטריצה טובה מגודל $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$).