실현 가능한 반올림

각 소수를 내림 또는 올림한 정수로 바꾸면서 모든 행 합과 열 합이 주어진 값과 일치하도록 하고, 그런 표 중 사전순으로 가장 앞선 것을 구한다.

어려움8그리디행렬구현수학면접 대비아직 제출이 없습니다시간 제한1초메모리 제한512 MB

문제

박 교수는 매일 실험에서 얻은 데이터 NN개를 기록한다. 각 데이터 값은 소수점 첫째 자리까지의 실수로 적혀 있다. MM일 동안의 기록은 MMNN열 표로 정리되고, 표에는 각 행의 합과 각 열의 합도 함께 적혀 있다.

이 표를 논문에 실으려면 데이터 값과 행의 합과 열의 합이 모두 정수여야 한다. 표에 적힌 실수 xxx\lfloor x \rfloor 또는 x\lceil x \rceil로 바꿀 수 있다. 바꾼 뒤에 모든 행에서 데이터 값 NN개의 합이 그 행의 합과 같고, 모든 열에서 데이터 값 MM개의 합이 그 열의 합과 같으면, 새 표를 실현 가능한 반올림 표라고 한다.

원래 표가 주어지면 실현 가능한 반올림 표를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 MMNN이 주어진다. MM은 실험 일수이고 NN은 하루에 기록하는 데이터 개수이다 (2M2002 \le M \le 200, 2N2002 \le N \le 200).

다음 MM개의 줄에는 각각 실수가 N+1N+1개씩 주어진다. ii번째 줄의 앞쪽 NN개는 ii일째 데이터 값이고, 마지막 하나는 ii번째 행의 합이다. 그다음 줄에는 열의 합 NN개가 주어진다.

모든 실수는 소수점 첫째 자리까지 주어지고, 데이터 값은 0.00.0 이상 1000.01000.0 이하이다. 각 행의 합은 그 행 데이터 값의 합과 정확히 같고, 각 열의 합은 그 열 데이터 값의 합과 정확히 같다.

출력

M+1M+1개의 줄을 출력한다. ii번째 줄에는 ii일째 데이터 값 NN개를 정수로 바꾼 값과 ii번째 행의 합을 정수로 바꾼 값을 공백 하나로 구분해 출력한다. 마지막 줄에는 열의 합 NN개를 정수로 바꾼 값을 공백 하나로 구분해 출력한다.

실현 가능한 반올림 표는 여러 개일 수 있다. 출력하는 정수를 위에서 정한 순서대로 나열한 수열을 비교해서 사전순으로 가장 작은 표를 출력한다. 실현 가능한 반올림 표는 항상 존재한다.