Description

There is an unknown $4 \times 4$ grid $M$, where each entry is a positive integer. You are given the sums of the $4$ rows, the sums of the $4$ columns, and the sums of both diagonals. In addition, the values of any $4$ positions in the grid are given; their positions are specified in the input.

Write a program to determine the positive integers in the remaining $12$ positions of the grid, such that the row sums, column sums, and diagonal sums match the values provided in the input.

You may assume that no row, column, or diagonal sum exceeds $300$. You may also assume that a solution always exists for the given input.

Input Format

The input contains $22$ space-separated positive integers.

The first four numbers are the sums of the four rows, respectively; the next four numbers are the sums of the $4$ columns. The next number is the sum of the main diagonal elements, i.e., $M(0, 0)+M(1,1)+M(2, 2)+M(3, 3)$. The following number (the $10$th number) is the sum of the anti-diagonal elements, i.e., $M(0, 3)+M(1, 2)+M(2, 1)+M(3, 0)$. The remaining part contains $12$ numbers, grouped into triples $i, j, k$, meaning $M(i,j)=k$.

Output Format

Output the $16$ numbers arranged as a $4 \times 4$ grid; within each row, separate the four numbers by a single space. Note: For a given input, there may be more than one valid solution. Any one of them is acceptable.

130 120 172 140 157 93 144 168 66 195 0 1 15 1 3 49 2 2 16 3 0 33

22 15 28 65
49 1 21 49
53 76 16 27
33 1 79 27

Hint

• For $10\%$ of the testdata, no row, column, or diagonal sum exceeds $20$.
• For $30\%$ of the testdata, no row, column, or diagonal sum exceeds $80$.
• For $60\%$ of the testdata, no row, column, or diagonal sum exceeds $200$.
• For $100\%$ of the testdata, no row, column, or diagonal sum exceeds $300$.

Thanks to @Jomoo for the contribution.

Translated by ChatGPT 5