마슈 반데드와 마법사의 격자판
시간 제한1초메모리 제한1024 MB
N×N 격자에 0 이상의 정수를 채워 인접한 칸끼리 정확히 1만큼 차이 나고 전체 합이 K가 되는지 판별하고, 가능하면 배치를 출력합니다.
문제
신각자 선발 시험에서 우수한 성과를 거둔 마슈 반데드는 신각자의 자격을 증명하기 위한 마지막 시련 하나만 남겨두고 있다. 마슈가 받은 마지막 시련의 내용은 다음과 같다.
더도 말고 덜도 말고 만 같아라
마법계의 관용어와 속담에 익숙하지 않은 당신을 위해 시련을 쉬운 말로 옮기면 다음과 같다.
- 개의 동전을 크기의 격자판에 배치해서, 이 격자판을 마법사의 격자판으로 만들어라. 각 칸에 개 이상의 동전을 놓았을 때 서로 인접한 모든 두 칸의 동전 개수 차이가 정확히 이면, 이 격자판을 마법사의 격자판이라고 한다.
마슈도 시련의 뜻을 이해하지 못했다. 감독관이 한눈을 파는 사이 마슈가 매우 빠르게 당신에게 도움을 청할 것이다. 마슈에게 위 시련에 맞는 마법사의 격자판을 만들 수 있는지 알려주고, 만들 수 있다면 격자판을 어떻게 만들어야 하는지 알려주어라.
입력
첫 번째 줄에 양의 정수 과 가 공백으로 구분되어 주어진다.
출력
개의 동전을 전부 사용해 마법사의 격자판을 만들 수 없다면 -1을 출력한다.
그렇지 않다면 다음 개의 줄에 개의 정수를 공백으로 구분하여 출력한다. 번째 줄의 번째 수는 격자판의 행 열 칸에 배치한 동전의 수를 의미한다.