Өлшемі $N$ болатын жақсы матрица дегеніміз — әрбір жолының, әрбір бағанының және екі диагоналінің жалпы XOR мәні $0$-ге тең болатын оң бүтін сандардан тұратын $N \times N$ матрица.

Дәлірек айтқанда, егер $N \times N$ өлшемді $A$ матрицасы төмендегі шарттардың барлығын қанағаттандырса, ол өлшемі $N$ болатын жақсы матрица деп аталады. Мұндағы $x \oplus y$ арқылы $x$ пен $y$ сандарының бит бойынша XOR операциясы белгіленген, ал $\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$ шығарыңыз.

Егер ол бар болса, бірінші жолға барлық элементтердің мүмкін болатын ең кіші жалпы қосындысын шығарыңыз.

Содан кейін келесі $N$ жолда элементтерін бос орынмен бөліп, $A$ матрицасын шығарыңыз. Яғни, $(i+1)$-ші жолда $A$ матрицасының $i$-ші жолының элементтері бос орын арқылы жазылуы тиіс.

Егер шешімдер бірнешеу болса, олардың кез келгенін шығаруға болады.

Мысалдар

1-мысал кірісі

2

1-мысал шығысы

4
1 1
1 1

2-мысал кірісі

1

2-мысал шығысы

-1

Ескертпе

Бірінші мысал үшін әрбір жолдың, әрбір бағанның және екі диагональдің жалпы XOR мәні $0$-ге тең, сондықтан ол жақсы матрица шарттарын қанағаттандырады. Сондай-ақ, өлшемі $2$ болатын барлық жақсы матрицалардың ішінде барлық элементтердің қосындысын $4$-тен кіші ету мүмкін емес, сондықтан ең кіші мән $4$-ке тең.

Екінші мысал үшін өлшемі $1$ болатын жақсы матрица жоқ, сондықтан $-1$ шығарыңыз.

Теріс емес бүтін $x, y$ сандарының бит бойынша XOR операциясы $x \oplus y$ келесідей анықталады.

• $x \oplus y$ санының екілік жазылуында $2^k$ ($k \ge 0$) разрядындағы цифр тек $x$ және $y$ сандарының екілік жазылуларындағы $2^k$ разрядындағы цифрлардың дәл біреуі $1$-ге тең болғанда ғана $1$-ге тең болады; әйтпесе ол $0$-ге тең.

Мысалы, $3 \oplus 5 = 6$ (екілік жүйеде $011 \oplus 101 = 110$).