짝수가 싫어

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

요약
2050×2050 격자에 0과 1을 채워 a*b = K인 모든 a×b 부분 직사각형의 1 개수가 홀수가 되도록 하거나, 불가능하면 -1을 출력한다.
난이도

어려움10점 중 8점

유형
수학, 정수론, 조합론, 구현
정답자
아직 제출이 없습니다

문제

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

서진이는 이 N2N^2개의 격자들에 원하는 대로 격자 당 최대 하나의 돌을 채울 수 있다. 이때 서진이는 짝수를 싫어하기 때문에 다음과 같은 규칙으로 돌을 채우고자 한다.

어떤 양의 정수 KK가 주어졌을 때, K=a×bK=a\times b를 만족하는 모든 양의 정수 aa, bb에 대해, 격자판 내의 격자들을 골라 만들 수 있는 a×ba\times b 형태의 직사각형을 생각하자. 이렇게 고를 수 있는 모든 직사각형에 대해, 해당 직사각형의 KK개의 격자 중 돌이 들어있는 격자의 개수를 직사각형의 값이라고 하자. 서진이는 짝수를 싫어하기 때문에 직사각형의 값이 짝수인 조건을 만족하는 직사각형이 단 하나도 존재하지 않도록 하고 싶다.

이 조건을 만족하도록 N×NN\times N크기의 정사각형 판에 돌을 채워보자.

입력

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

출력

만약 조건을 만족하도록 N×NN\times N 정사각형 모양의 격자판을 채울 수 있다면, NN개의 줄에 걸쳐 각 격자의 상태를 나타내는 정수 NN개를 순서대로 공백으로 구분해 출력한다. 1은 그 격자에 돌을 채우는 것을, 0은 그 격자에 돌을 채우지 않는 것을 의미한다.

만약 조건을 만족하도록 N×NN\times N 정사각형 모양의 격자판을 채울 수 없다면 격자판 대신 -1을 하나 출력한다.

예제3

  1. 예제 1

    입력
    3 3
    
    예상 출력
    1 0 0
    0 1 0
    0 0 1
    
  2. 예제 2

    입력
    4 8
    
    예상 출력
    0 0 0 1
    0 0 0 0
    0 0 0 1
    1 0 1 0
    
  3. 예제 3

    입력
    4 15
    
    예상 출력
    0 0 0 0
    0 0 0 0
    0 0 0 0
    0 0 0 0