시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 109 46 45 44.118%

문제

11 살 근우는 쌓기 나무를 좋아한다. 근우는 수학 교과서의 문제를 풀다가 재미있는 것을 찾았다. 바로 쌓기 나무가 쌓인 모양을 위, 앞, 오른쪽 옆에서 바라보고 쌓기 나무가 쌓인 모양을 유추하는 문제를 푸는 것이다.

근우는 똑똑하기 때문에 수학 교과서에 있는 쌓기 나무 문제를 모두 푸는 것은 어려운 일이 아니었다. 근우는 혹시 이러한 쌓기 나무 문제를 푸는 프로그램이 존재하는지 궁금해졌지만, 프로그램을 찾지는 못했다. 그래서 여러 분들에게 이러한 프로그램을 만들어 달라고 요청하였다. 근우를 위해 프로그램을 만들어보자!

답이 여러 개가 있을 수 있는데, 답으로 가능한 것들 중에서 쌓기 나무를 가장 많이 사용하는 것을 출력하면 된다.

입력

첫째 줄에 세로 길이 N 과 가로 길이 M 이 띄어쓰기로 구분되어 주어진다. (1<=N, M<=500)

둘째 줄부터 N+1 번째 줄까지 위에서 바라본 모양이 주어진다. 쌓기나무가 있는 위치는 1, 그렇지 않은 위치는 0 으로 표시된다.

N+2 번째 줄에 앞에서 바라본 모양(0<=높이<=100)이 한 줄로 주어진다.

N+3 번째 줄에 오른쪽 옆에서 바라본 모양(0<=높이<=100)이 한 줄로 주어진다.

출력

주어진 데이터를 바탕으로, 가능한 쌓기 나무 모양 중에서 가장 쌓기 나무를 많이 사용하는 경우를 출력하여라. 주어진 데이터를 만족하는 쌓기나무가 존재하지 않는 경우에는 -1 을 출력하라.

예제 입력

2 3
0 1 0
1 1 1
1 4 3
3 4

예제 출력

0 4 0
1 3 3

힌트