크기 $N$의 좋은 행렬(good matrix)이란 각 행, 각 열, 그리고 두 대각선의 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$).