Maxplus

Max-plus algebra works over the real numbers with only two binary operations: the maximum operation $\oplus$ and the addition operation $\otimes$. The operation $\otimes$ binds tighter than $\oplus$.

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

For example, $3 \oplus 5 = 5$, $7 \oplus 4 = 7$, $3 \otimes 5 = 8$, and $7 \otimes 4 = 11$.

Applications of this algebra often use the max-plus product of two matrices, $A \otimes B = C$. The product is defined the same way as the ordinary matrix product, except that the multiplication sign becomes $\otimes$ (addition) and the addition sign becomes $\oplus$ (maximum).

This problem only deals with the max-plus product of $3 \times 3$ integer matrices.

$\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}$

Here $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}$, so $c_{i,j}$ is the largest of the three sums of matching entries.

For example, the following holds.

$\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}$

You are given the matrices $A$ and $C$. Every entry of both matrices is an integer with absolute value less than 100. Write a program that finds a matrix $B$ whose entries are integers with absolute value less than 1000 and that satisfies $A \otimes B = C$, or reports that no such matrix exists.

The first three lines contain three integers each, the matrix $A$.

The next three lines contain three integers each, the matrix $C$.

Every number is an integer with absolute value less than 100.

If no matrix $B$ satisfies $A \otimes B = C$, print nemoguce on the first and only line.

Otherwise print the matrix $B$ on three lines, three integers per line, separated by single spaces.

Several matrices can satisfy $A \otimes B = C$. Print the one whose every entry is greater than or equal to the entry in the same position of every other valid matrix. Whenever at least one valid matrix exists, that matrix exists and is unique, and all of its entries have absolute value less than 1000.