맥스플러스

맥스플러스 대수는 실수 위에서 이항 연산 두 개만 쓰는 대수 체계다. 하나는 최댓값 연산 $\oplus$이고 다른 하나는 덧셈 연산 $\otimes$이며, $\otimes$가 $\oplus$보다 우선순위가 높다.

$x \oplus y = \max(x, y), \qquad x \otimes y = x + y$

예를 들어 $3 \oplus 5 = 5$, $7 \oplus 4 = 7$, $3 \otimes 5 = 8$, $7 \otimes 4 = 11$이다.

이 대수를 응용할 때는 두 행렬의 맥스플러스 곱 $A \otimes B = C$를 많이 쓴다. 곱은 보통의 행렬 곱과 같은 꼴로 정의하되, 곱셈 기호를 $\otimes$(덧셈)로 바꾸고 덧셈 기호를 $\oplus$(최댓값)로 바꾼다.

이 문제에서는 정수로 이루어진 $3 \times 3$ 행렬의 맥스플러스 곱만 다룬다.

$\begin{bmatrix} a_{1,1} & a_{1,2} & a_{1,3} \\ a_{2,1} & a_{2,2} & a_{2,3} \\ a_{3,1} & a_{3,2} & a_{3,3} \end{bmatrix} \otimes \begin{bmatrix} b_{1,1} & b_{1,2} & b_{1,3} \\ b_{2,1} & b_{2,2} & b_{2,3} \\ b_{3,1} & b_{3,2} & b_{3,3} \end{bmatrix} = \begin{bmatrix} c_{1,1} & c_{1,2} & c_{1,3} \\ c_{2,1} & c_{2,2} & c_{2,3} \\ c_{3,1} & c_{3,2} & c_{3,3} \end{bmatrix}$

여기서 $c_{i,j} = a_{i,1} \otimes b_{1,j} \oplus a_{i,2} \otimes b_{2,j} \oplus a_{i,3} \otimes b_{3,j}$이다. 즉 $c_{i,j}$는 대응하는 성분들의 합 세 개 중 가장 큰 값이다.

예를 들어 다음이 성립한다.

$\begin{bmatrix} 0 & 1 & 2 \\ 3 & -1 & 0 \\ 1 & 1 & 1 \end{bmatrix} \otimes \begin{bmatrix} 2 & 0 & 1 \\ -1 & 3 & 2 \\ 0 & 1 & 0 \end{bmatrix} = \begin{bmatrix} 2 & 4 & 3 \\ 5 & 3 & 4 \\ 3 & 4 & 3 \end{bmatrix}$

행렬 $A$와 $C$가 주어진다. 두 행렬의 성분은 모두 절댓값이 100보다 작은 정수다. $A \otimes B = C$를 만족하고 성분이 모두 절댓값이 1000보다 작은 정수인 행렬 $B$를 찾는 프로그램을 작성하시오. 그런 행렬이 없으면 없다는 사실을 출력한다.

첫 세 줄에 행렬 $A$의 성분이 한 줄에 세 개씩 주어진다.

다음 세 줄에 행렬 $C$의 성분이 한 줄에 세 개씩 주어진다.

모든 수는 절댓값이 100보다 작은 정수다.

$A \otimes B = C$를 만족하는 행렬 $B$가 없으면 첫 줄에 nemoguce만 출력한다.

있으면 세 줄에 걸쳐 행렬 $B$의 성분을 한 줄에 세 개씩 공백 하나로 구분해 출력한다.

조건을 만족하는 $B$는 여러 개일 수 있다. 그중에서 모든 자리의 성분이 다른 어떤 답의 같은 자리 성분보다 크거나 같은 행렬을 출력한다. 답이 하나라도 있으면 그런 행렬은 항상 존재하고 유일하다. 그 행렬의 성분은 모두 절댓값이 1000보다 작다.