Problem I
Mix-and-Matrix

Figure 1: An example of matrix multiplication.

In order to fairly divide a piece of cake between children, what some parents will enforce is have one of them cut the cake into two slices and have the other choose which slice they want. Assuming both want as much cake as possible, the best strategy in this case is for the first child to cut the cake perfectly evenly.

You and your brother have found yourselves in a similar dilemma. At your recent Christmas party, your math-loving relatives have gifted you two some matrices but were too busy singing along to Mariah Carey to specify who gets which of them. Now, you’re in charge of splitting your gifts properly, but the definition of an even split is oddly specific here. Namely, together you have four square matrices and want to split them into groups of two such that the product of the first two equals the product of the last two. You may recall that the definition of the product between an $m \times k$ matrix $A$ and a $k \times n$ matrix $B$ is a new $m\times n$ matrix $C$ such that $\forall i \in \{ 1, 2, \ldots , m\} , j \in \{ 1, 2, \dots , n\} \text{, we have } C_{ij} = \sum _{t=1}^{k} A_{it}B_{tj}$. As matrix multiplication is not commutative, the order will matter within the two groups.

Since you’ll be splitting the gifts, your brother will take care of selecting which ones he gets and which ones you’re left with. In fact, he is so hands-off about your method of splitting the matrices that he doesn’t even mind if you decide to go with a randomized algorithm that has a nonzero (albeit, very low) probability of being incorrect. When it comes time for him to get his matrices (or for our automated judge to check your answer), though, it better be correct.

If there are multiple ways to split the matrices into $2$ groups of two, you can answer with any of them.

Input

The first line of the input contains an integer $n$ ($1 \leq n \leq 1\, 000$), which will be used to define the size of the square matrices. Following this are $n$ lines each containing $n$ space-separated integers, containing the elements of the $n\times n$ matrix $A$. The matrices $B$, $C$, and $D$ are given in the same format afterward, in this order, and they each have the same size. Every element $M_{ij}$ of each matrix $M$ ($M \in \{ A, B, C, D\} $) in the input is an integer that satisfies $-1\, 000 \leq M_{ij} \leq 1\, 000$.

Output

If there exists an assignment of $(A, B, C, D)$ to $(M_1, M_2, M_3, M_4)$ that satisfies $M_1 M_2 = M_3 M_4$, then print out $M_1$ and $M_2$ on one line and $M_3$ and $M_4$ on the second line. Any such assignment will be accepted if it meets these conditions. If there is no such assignment, then print out “No solution.” (including the period).

2
2 1
1 1
1 1
0 1
1 -1
0 1
1 -1
-1 2

A D
B C

3
4 3 1
3 4 1
9 5 1
2 2 8
8 8 4
6 4 8
8 6 2
6 8 2
18 10 2
1 1 4
4 4 2
3 2 4

A B
C D

3
1 0 0
0 1 0
0 0 1
1 2 3
4 5 6
7 8 9
1 2 3
4 5 6
7 8 9
1 0 0
0 1 0
0 0 1

D B
A C

2
3 1
4 1
5 9
2 6
5 3
5 8
9 7
9 3

No solution.