마작 거신병 1

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

요약
1만 C장과 9만 D장을 H행 W열 격자에 배치해 각 행의 합이 위에서 아래로 엄격히 커지도록 만들고, 불가능하면 -1을 출력합니다.
난이도

보통10점 중 4점

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

문제

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

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

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

마작 거신병의 안정적인 구조를 위해, 아래 행에 쓰여 있는 모든 수의 합은 위 행에 쓰여 있는 모든 수의 합보다 커야 합니다. 다시 말해:

  • ii행에 놓여 있는 마작패들에 쓰여 있는 수의 합을 S_iS\_i라고 했을 때, 1≤i\<j≤H1 \le i\<j \le H인 정수 ii, jj에 대해 S_i\<S_jS\_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만의 개수와 9만의 개수 CC와 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행에 놓여 있는 마작패들에 쓰여 있는 수의 합을 S_iS\_i라고 했을 때, 1≤i\<j≤H1 \le i\<j \le H인 정수 ii, jj에 대해 S_i\<S_jS\_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