System of equations#2994
Sign in

System of equations

1 second
64 megabytes
Very hard

Let the -th equation of a system of equations be as follows:

X + Y = b_k

where

X = x_{1k} + x_{2k} + \dots + x_{k-1, k}
Y = x_{k, k+1} + \dots + x_{kN}

Thus, the left side of each equation contains (N-1) terms, and each unknown appears in exactly two equations of the system.

Write a program that, given b_1, \dots, b_N, finds one solution to the system, under the condition that the unknowns x_{ij} can take only the values or .

Input

The first line of the input file contains a natural number — the number of test cases. Each test case starts with a line containing the number (3 \leq N \leq 50) — the number of equations in the system. The second line of each test case contains integers b_i (0 \leq b_i \leq 50).

Output

For each test case, output one solution to the system: (N-1) lines, each -th of which contains N-k numbers — the found values of the unknowns:

x_{12}\ \ldots\ x_{1N} \\ x_{23}\ \ldots\ x_{2N} \\ x_{34}\ \ldots\ x_{3N} \\ \ldots \\ x_{N-1, N}

If the system has no solutions for a test case, output a single line containing .

Examples

Example 1

Loading
Loading