P12976 Force Analysis Force

Comentropy, who was still writing problems, suddenly received a challenge—surprisingly, it was a mechanics problem. He was shocked, but once he saw the Constraints, he immediately knew how to solve it. However, the process was long and tedious, so he asked you to help simplify it. Note: This problem has no strict physical theory behind it, and it does not require any physics background. **It is recommended to read the formal statement.**

There are $n \times n$ cubic blocks arranged in a square grid. Each block has its own weight, and you need to keep them balanced and stationary. This requires that for the block in row $i$ and column $j$, the supporting force on its bottom face must lie within the interval $[l_{i,j}, r_{i,j}]$. The problem setters provide $n$ steel wires in the horizontal direction and $n$ steel wires in the vertical direction to provide the supporting force, and place the blocks at the wire intersection points. Now you can apply forces to these $2n$ wires separately. (Note that the force is the same everywhere along the same wire.) Definition: Numerically, the supporting force received by a block equals the sum of the forces you apply to the two wires beneath it.  As shown in the figure, one set of wires is placed horizontally, with applied forces $[x_1, x_2, \dots, x_n]$; the other set is placed vertically, with applied forces $[y_1, y_2, \dots, y_n]$. The resultant force at intersection $(i, j)$ is $x_i + y_j$. Please find the force applied to each wire. To make it harder for Comentropy, the setters also require the sequence $[x_1, x_2, \dots, x_n, y_1, y_2, \dots, y_n]$ to be lexicographically smallest. Can you help him handle this problem? **Each force must be a non-negative integer, pointing upward.** **Formally**: Given two $n \times n$ matrices $l, r$, find non-negative integer sequences $\{x\}$ and $\{y\}$ such that $l_{i,j} \leq x_i + y_j \leq r_{i,j}$. Among all solutions, output the one that makes the combined sequence $[x_1, x_2, \dots, x_n, y_1, y_2, \dots, y_n]$ lexicographically smallest.

The first line contains a positive integer $n(1 \leq n \leq 500)$, indicating an $n \times n$ matrix. Lines $2$ to $n+1$ contain a matrix representing the lower bounds $l$. Lines $n+2$ to $2n+1$ contain another matrix representing the upper bounds $r$.

If there is no solution, output ```-1``` directly. Otherwise: The first line contains $n$ numbers, representing the forces on the horizontal wires $x_1, \ldots, x_n$. The second line contains $n$ numbers, representing the forces on the vertical wires $y_1, \ldots, y_n$. **Note: If there are multiple answers, output the lexicographically smallest one.**

**Sample 1 Explanation:** There may be another solution with $x_1 = 2, x_2 = 2, y_1 = 0, y_2 = 3$, but $\{0, 0\}, \{2, 5\}$ is a lexicographically smaller solution, and it can be proven to be lexicographically smallest. For $10\%$ of the testdata, it is guaranteed that $1 \leq n \leq 7, 0 \leq r_{i,j} \leq 7$. For $20\%$ of the testdata, it is guaranteed that $1 \leq n \leq 50$, $1 \leq l_{i,j} \leq r_{i,j} \leq 200$. For $40\%$ of the testdata, it is guaranteed that $1 \leq n \leq 200$. For the remaining $20\%$ of the testdata, it is guaranteed that $l_{i,j} = r_{i,j}$. For $100\%$ of the testdata, it is guaranteed that $1 \leq n \leq 500$, $0 \leq l_{i,j} \leq r_{i,j} \leq 10^9$. **Please pay attention to the impact of constants on the running efficiency of your program.** Translated by ChatGPT 5