짝수가 싫어
시간 제한1초메모리 제한1024 MB
2050×2050 격자에 0과 1을 채워 a*b = K인 모든 a×b 부분 직사각형의 1 개수가 홀수가 되도록 하거나, 불가능하면 -1을 출력한다.
문제
한 변의 길이가 인 정사각형 모양의 격자판이 있다.
서진이는 이 개의 격자들에 원하는 대로 격자 당 최대 하나의 돌을 채울 수 있다. 이때 서진이는 짝수를 싫어하기 때문에 다음과 같은 규칙으로 돌을 채우고자 한다.
어떤 양의 정수 가 주어졌을 때, 를 만족하는 모든 양의 정수 , 에 대해, 격자판 내의 격자들을 골라 만들 수 있는 형태의 직사각형을 생각하자. 이렇게 고를 수 있는 모든 직사각형에 대해, 해당 직사각형의 개의 격자 중 돌이 들어있는 격자의 개수를 직사각형의 값이라고 하자. 서진이는 짝수를 싫어하기 때문에 직사각형의 값이 짝수인 조건을 만족하는 직사각형이 단 하나도 존재하지 않도록 하고 싶다.
이 조건을 만족하도록 크기의 정사각형 판에 돌을 채워보자.
입력
첫 번째 줄에 과 가 공백으로 구분되어 주어진다.
출력
만약 조건을 만족하도록 정사각형 모양의 격자판을 채울 수 있다면, 개의 줄에 걸쳐 각 격자의 상태를 나타내는 정수 개를 순서대로 공백으로 구분해 출력한다. 1은 그 격자에 돌을 채우는 것을, 0은 그 격자에 돌을 채우지 않는 것을 의미한다.
만약 조건을 만족하도록 정사각형 모양의 격자판을 채울 수 없다면 격자판 대신 -1을 하나 출력한다.