스타 대결

각 선수가 치러야 할 경기 수가 행과 열로 주어질 때, 행 우선 사전순으로 가장 작은 0/1 행렬을 만들고, 가능한 표가 없으면 -1을 출력한다.

보통7그리디그래프구현수학면접 대비아직 제출이 없습니다시간 제한2초메모리 제한128 MB

문제

서울 서쪽에서 스타크래프트를 가장 잘하는 팀은 지민이네 팀이고, 동쪽에서 가장 잘하는 팀은 한수네 팀이다. 두 팀은 누가 서울 최고인지 가리기 위해 대결을 벌이기로 했다.

지민이네 팀은 NN명, 한수네 팀은 MM명이다. 각 선수는 자신이 치러야 하는 경기 수가 정해져 있으며, 이 값은 선수마다 다를 수 있다.

대진표는 다음 규칙을 모두 만족해야 한다.

  1. 모든 경기는 지민이네 팀 한 명과 한수네 팀 한 명이 맞붙는다.
  2. 같은 상대와의 대결은 최대 한 번만 할 수 있다.
  3. 모든 선수는 자신에게 정해진 경기 수만큼 정확히 경기를 치러야 한다.
  4. 조건을 만족하는 대진표가 여러 개라면 사전순으로 가장 앞서는 것을 고른다.

대진표는 N×MN \times M 행렬로 나타낸다. 행은 지민이네 팀, 열은 한수네 팀에 대응한다. (i,j)(i, j) 칸이 11이면 지민이네 ii번 선수와 한수네 jj번 선수가 대결하는 것이고, 00이면 대결하지 않는 것이다.

두 대진표의 사전순 비교는 다음과 같이 정의한다. 먼저 두 행렬에서 처음으로 달라지는 행 ii를 찾고, 그 행에서 처음으로 달라지는 열 jj를 찾는다. 그 칸 (i,j)(i, j)00인 대진표가 사전순으로 더 앞선다.

각 팀 선수들이 치러야 하는 경기 수가 주어질 때, 사전순으로 가장 앞서는 대진표를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 지민이네 팀의 인원 NN과 한수네 팀의 인원 MM이 주어진다. 둘째 줄에는 지민이네 팀의 각 선수가 치러야 하는 경기 수가, 셋째 줄에는 한수네 팀의 각 선수가 치러야 하는 경기 수가 주어진다. NNMM5050 이하의 자연수이고, 각 경기 수는 5050 이하의 자연수 또는 00이다.

출력

대진표를 NN개의 줄에 출력한다. 각 줄은 그 행의 값을 공백 없이 이어 붙인 MM자리 문자열이다. 조건을 만족하는 대진표가 없으면 1-1을 출력한다.