만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

마작 거신병 1

면접 대비

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

요약
H행 W열 격자에 1 타일 C개와 9 타일 D개를 모두 채워, 아래 행의 합이 위 행의 합보다 항상 크도록 만듭니다. 불가능하면 -1을 출력합니다.
난이도

보통10점 중 5점

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

문제

여러분은 마작에서 이기기 위해 마작 거신병을 소환하려고 합니다.

마작 거신병은 총 H×WH \times W장의 마작패로 이루어진 HH행 WW열의 직사각형 모양입니다.

아름다운 마작 거신병을 소환하기 위해 1만과 9만으로만 이루어진 마작 거신병을 만들려고 합니다. 1만에는 11이, 9만에는 99가 하나씩 쓰여 있습니다.

마작 거신병의 안정적인 구조를 위해, ii행에 놓인 마작패에 쓰인 수의 합을 SiS_i라고 합니다. 아래 행에 쓰인 수의 합은 위 행에 쓰인 수의 합보다 커야 합니다. 즉, 1≤i<j≤H1 \le i < j \le H인 모든 정수 ii, jj에 대해 Si<SjS_i < S_j이어야 합니다.

가지고 있는 CC장의 1만과 DD장의 9만으로 안정적이고 아름다운 마작 거신병을 소환해 주세요.

입력

첫 번째 줄에 마작 거신병의 모양을 나타내는 두 정수 HH와 WW가 공백으로 구분되어 주어집니다. (H,W≥1(H, W \ge 1, H×W≤100 000)H \times W \le 100\,000)

두 번째 줄에 가지고 있는 1만의 개수 CC와 9만의 개수 DD가 공백으로 구분되어 주어집니다. (C,D≥0(C, D \ge 0, C+D=H×W)C + D = H \times W)

출력

안정적이고 아름다운 마작 거신병의 구조를 출력합니다.

  • 출력은 HH개의 줄로 이루어집니다.
  • ii번째 줄에는 ii행에 놓을 마작패 WW장을 공백으로 구분하여 순서대로 출력합니다. 1만이면 11, 9만이면 99를 출력합니다.
  • ii행에 놓인 마작패에 쓰인 수의 합을 SiS_i라고 할 때, 1≤i<j≤H1 \le i < j \le H인 모든 정수 ii, jj에 대해 Si<SjS_i < S_j이어야 합니다.

여러 방법이 있다면 그중 하나를 출력합니다. 어떻게 해도 안정적이고 아름다운 마작 거신병을 만들 수 없다면 -1을 출력합니다.

예제2

  1. 예제 1

    입력
    3 6
10 8
    예상 출력
    1 1 9 1 1 1
1 9 1 1 9 1
9 9 9 9 1 9

  2. 예제 2

    입력
    6 2
5 7
    예상 출력
    -1