Matrix Preliminaries

(He who has already studied linear algebra may skip this part) A matrix is composed of n × n elements. Formally, is an n × n matrix. For example, A= Two operations on matrices will be used in this problem: and  an1 an2 ··· ann () a11 a12 ··· a1n a21 a22 ··· a2n  A= . . ... .  is a 2×2 matrix.

1. A + k (A is an n × n matrix, k is an integer) all the elements in the MAIN diagonal is added by k. That is For example, A−k is defined A+(−k), so 34 3−1 2. A∗B (both A and B are n×n matrices). Let 12 34  an1 an2 ··· ann+k ()() 12+5=62 34 39 ()() a11 + k a12 · · · a1n  a21 a22 + k · · · a2n  A+k= . . ... .  12 −42 −5=  a11 a12 ··· a1n b11 b12 ··· b1n a21 a22 ··· a2n  b21 b22 ··· b2n  A=....,B=....  . . .. .   . . .. .  an1 an2 ··· ann bn1 bn2 ··· bnn  c11 c12 ··· c1n c21 c22 ··· c2n  C=A×B= . . ... .  cn1 cn2 ··· cnn

10565 – Matrix 2/3 then we have: For example, For example, () 12 34 ∑n k=1 ()()( )() 1 2 × 5 6 = 5+14 6+16 = 19 22 3 4 7 8 15+28 18+32 43 50 cij = aikbkj = ai1b1j +ai2b2j +···+a1nbnj Well, I have no time to explain why matrix multiplication is defined like this. Please just remember it. Problem Find a matrix root of this equation: (A+k1)(A+k2)(A+k3)...(A+km) = 0 where k1,k2,...,km are distinct integers. That is, EVERY ELEMENT OF the matrix computed from the left is zero. is a matrix root of the equation (A + 1)(A − 5) = 0 since ()()()() 1 2 (A + 1)(A − 5) = × −4 4 2 −2

−8+8 8−8 −8+8 8−8

0 0 0 0 3 4 A= It can be proven that there are infinitely many solutions, however, I do not like trivial answer, so your answer must have at least (n ∗ n)/2 non-zero elements. Input The first line contains the number of tests t (1 ≤ t ≤ 15). Each case contains two lines. The first line contains an integer m (1 ≤ m ≤ 30). The second line contains m integers, representing k1, k2, . . . , km respectively. Absolute values of the integers are no greater than 100. Output For each test case, if no answer can be found, print ‘-1’. Otherwise print n, indicating that you found an n × n matrix root. The following n lines should be the matrix. It is guaranteed that if there is an answer, the smallest possible n is not greater than 50, so your n should also NOT be greater than 50. The absolute value of integers you gave should not be larger than 1000. Sample Input 2 2 1 -5 2 1 -5

10565 – Matrix 3/3 Sample Output 2 14 23 2 14 23