마슈 반데드와 마법사의 격자판

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

요약
N과 K가 주어질 때, 인접한 두 칸의 동전 수 차이가 정확히 1이 되도록 K개의 동전을 모두 써서 N×N 격자판을 만들고, 불가능하면 -1을 출력한다.
난이도

보통10점 중 6점

유형
그리디, 수학, 구현, 완전 탐색
정답자
아직 제출이 없습니다

문제

신각자 선발 시험에서 우수한 성과를 이루어낸 마슈 반데드는, 마지막으로 신각자의 자격을 증명하기 위한 단 하나의 시련만을 남겨두고 있다! 마슈가 받은 마지막 시련의 내용은, 다음과 같다.

더도 말고 덜도 말고 KK만 같아라

마법계의 관용어와 속담에 대해서 잘 모르는 당신을 위해 시련을 알기 쉽게 번역하면, 다음과 같다:

  • KK개의 동전을 N×NN\times N 크기의 격자판에 배치해서, 이 격자판을 마법사의 격자판으로 만들어라. 격자판의 각 칸에 00개 이상의 동전을 배치해 격자판에서 모든 인접한 두 칸의 동전 개수의 차이가 정확히 11일 때, 이 격자판을 마법사의 격자판이라고 한다.

물론 마슈 또한 시련을 이해하지 못한 것은 마찬가지이므로 시련의 감독관이 한눈을 파는 사이 매우 빠르게 당신에게 도움을 청할 것이다! 마슈를 위해 위의 시련에 맞는 마법사의 격자판을 만들 수 있는지 알려주고, 만들 수 있다면 격자판을 어떻게 만들어야 하는지 알려주어라.

입력

첫 번째 줄에 양의 정수 NN과 KK가 공백으로 구분되어 주어진다. (1≤N≤1,000;1≤K≤109)\left(1 \leq N \leq 1\\,000;1 \leq K \leq 10^9\right)

출력

만약 KK개의 동전을 전부 사용해 마법사의 격자판을 만들 수 없다면 −1을 출력한다.

그렇지 않다면 다음 NN개의 줄에 NN개의 정수를 공백으로 구분하여 출력한다. ii번째 줄의 jj번째 수는 격자판의 ii행 jj열 칸에 배치한 동전의 수를 의미한다.

예제2

  1. 예제 1

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

    입력
    3 1
    
    예상 출력
    -1