Blind Gauss

시간 제한1초메모리 제한2048 MB

요약

행렬식이 1이고 i번째 행에 홀수가 정확히 a_i개 있는 n×n 음이 아닌 정수 행렬을 만들거나, 불가능하면 -1을 출력한다.

난이도: 어려움10점 중 8점
유형: 수학, 조합론, 정수론, 구현
정답자: 아직 제출이 없습니다

문제

Construct a square matrix with $n$ rows and $n$ columns consisting of nonnegative integers from $0$ to $10^{18}$ such that its determinant is equal to $1$ and there are exactly $a\_i$ odd numbers in the $i$ -th row for each $i$ from $1$ to $n$ , or report that there is no such matrix.

입력

The first line contains a single integer $n$ ( $2 \le n \le 50$ ).

Each of the next $n$ lines contains a single integer $a\_i$ ( $1 \leq a\_i \leq n$ ).

출력

If there is no matrix that meets the requirements, output -1.

Otherwise, output $n$ lines with $n$ numbers $m\_{i,j}$ in each ( $0 \leq m\_{i,j} \leq 10^{18}$ ): the elements of the constructed matrix. If there are multiple solutions, print any one of them.

예제5

예제 1
입력
```
2
1
1
```
예상 출력
```
1 0
0 1
```
예제 2
입력
```
2
2
1
```
예상 출력
```
1 1
1 2
```

예제 3

입력

예상 출력

예제 4
입력
```
3
2
2
2
```
예상 출력
```
-1
```
예제 5
입력
```
3
3
1
3
```
예상 출력
```
-1
```