#P18044. Xor Magic Square

Xor Magic Square

Xor Magic Square

题目描述

称一个 N×NN\times N 的正整数矩阵 AA 为合法矩阵,当且仅当每一行、每一列以及两条主对角线上的所有元素的按位异或和都为 00。也就是说:

⨁j=1NAi,j=0(1≤i≤N),\bigoplus_{j=1}^N A_{i,j}=0\quad(1\le i\le N), ⨁i=1NAi,j=0(1≤j≤N),\bigoplus_{i=1}^N A_{i,j}=0\quad(1\le j\le N), $$\bigoplus_{i=1}^N A_{i,i}=\bigoplus_{i=1}^N A_{i,N-i+1}=0.$$

给定 NN,构造一个所有元素之和最小的合法矩阵。如果不存在合法矩阵,输出无解。

注意每个元素必须为正整数,不能为 00。

输入格式

输入一个整数 NN,1≤N≤20001\le N\le2000。

输出格式

若不存在合法矩阵,仅输出一行 -1。

否则,第一行输出最小的元素总和,接下来 NN 行输出矩阵,每行 NN 个正整数,以空格分隔。

若存在多种最优矩阵,输出任意一种。

样例 1

输入:

2

输出:

4
1 1
1 1

样例 2

输入:

1

输出:

-1