짝수가 싫어

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

요약

N×N 격자에 돌을 놓아, 넓이가 K인 모든 a×b 직사각형 안의 돌 개수가 홀수가 되게 하거나, 불가능하면 -1을 출력합니다.

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

문제

한 변의 길이가 $N=2\,050$ 인 정사각형 모양의 격자판이 있다.

서진이는 이 $N^2$ 개의 격자 각각에 원하는 대로 최대 하나의 돌을 채울 수 있다. 서진이는 짝수를 싫어하기 때문에 다음 규칙에 따라 돌을 채우고자 한다.

양의 정수 $K$ 가 주어졌을 때, $K=a\times b$ 를 만족하는 모든 양의 정수 $a$ , $b$ 에 대해 격자판 안에서 고를 수 있는 $a\times b$ 모양의 직사각형을 생각하자. 고른 직사각형의 $K$ 개 격자 중 돌이 들어 있는 격자의 개수를 직사각형의 값이라고 한다. 서진이는 직사각형의 값이 짝수인 직사각형이 하나도 없도록 하고 싶다.

이 조건을 만족하도록 $N\times N$ 크기의 격자판에 돌을 채워 보자.

입력

첫 번째 줄에 $N$ 과 $K$ 가 공백으로 구분되어 주어진다. ( $N=2\,050$ , $1\le K\le N^2$ )

출력

조건을 만족하도록 격자판을 채울 수 있다면, $N$ 개의 줄에 걸쳐 각 격자의 상태를 나타내는 정수 $N$ 개를 공백으로 구분해 출력한다. 1은 그 격자에 돌을 채우는 것, 0은 돌을 채우지 않는 것을 뜻한다.

조건을 만족하도록 격자판을 채울 수 없다면 격자판 대신 -1을 출력한다.

예제3

예제 1
입력
```
3 3
```
예상 출력
```
1 0 0
0 1 0
0 0 1
```
예제 2
입력
```
4 8
```
예상 출력
```
0 0 0 1
0 0 0 0
0 0 0 1
1 0 1 0
```
예제 3
입력
```
4 15
```
예상 출력
```
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
```