시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB339867252925.655%

문제

서울의 서쪽에서 스타를 가장 잘하는 팀은 지민이의 팀이고, 동쪽에서 가장 잘하는 팀은 한수의 팀이다.

두 사람은 누가 서울에서 가장 스타크래프트를 잘하는지 결정하기 위해 대결을 하기로 했다.

지민이의 팀은 총 N명, 한수의 팀은 총 M명이다. 모든 팀원은 한 사람당 해야 하는 경기의 수가 정해져 있다. 이 숫자는 사람마다 다를 수 있다.

경기 대진표는 다음과 같은 규칙을 지켜서 만들어야 한다.

  1. 모든 경기는 지민이의 팀 중 한 명, 한수의 팀 중 한 명이 대결한다.
  2. 같은 대결은 최대 한 번 할 수 있다.
  3. 모든 팀원은 한 사람당 해야 하는 경기의 수 만큼 경기를 해야 한다.
  4. 가능한 경기 대진표가 여러 가지라면 사전 순으로 가장 앞서는 것을 선택한다. 사전 순의 정의는 후술한다.

경기 대진표는 N*M 크기의 행렬이다. 행은 지민이의 팀에 대응하고, 열은 한수의 팀에 대응한다. (i,j)가 1이면 지민이의 팀의 i번 선수와 한수의 팀의 j번 선수가 대결을 하는 것이고, 0이면 대결을 하지 않는 것이다.

대진표의 사전 순 비교는 다음과 같이 정의된다. 두 대진표의 행 중에서 맨 처음으로 다른 행 i를 찾는다. 그리고 나서 그 행에서 가장 처음 다른 열 j를 찾는다. (i,j)가 0인 대진표가 사전 순으로 앞서는 대진표이다.

지민이의 팀의 각 팀원이 해야 하는 경기의 수, 한수의 팀의 각 팀원이 해야 하는 경기의 수가 주어졌을 때, 사전 순으로 가장 앞서는 대진표를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 지민이의 팀의 팀원 수 N과 한수의 팀의 팀원 수 M이 주어진다. 둘째 줄에는 지민이의 팀의 각 팀원이 해야 하는 경기의 수가 주어지고, 셋째 줄에는 한수의 팀의 각 팀원이 해야 하는 경기의 수가 주어진다. N과 M은 50보다 작거나 같은 자연수이고, 경기의 수는 50보다 작거나 같은 자연수 또는 0이다.

출력

대진표를 N개의 줄에 출력한다. 만약 가능한 대진표가 없으면 -1을 출력한다.

예제 입력 1

3 3
1 2 3
3 1 2

예제 출력 1

100
101
111

예제 입력 2

4 4
3 2 1 1
1 3 1 2

예제 출력 2

0111
0101
0100
1000

예제 입력 3

4 4
1 2 3 4
5 6 7 8

예제 출력 3

-1

예제 입력 4

2 3
47 47
47 40 7

예제 출력 4

-1

예제 입력 5

2 9
5 5
1 1 2 1 1 1 1 1 1

예제 출력 5

001001111
111110000

예제 입력 6

4 6
0 0 0 0
0 0 0 0 0 0

예제 출력 6

000000
000000
000000
000000

출처

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: jh05013