P8156 "PMOI-5" Strange Equations.

Given an integer $n$, there are $n \times n$ unknowns $a_{1}, a_{2}, \cdots, a_{n \times n}$. You are given $2 \times n$ equations. There are two types of equations, and each type has $n$ equations. The $i$-th equation of the first type is $\sum_{j=1}^n a_{(i-1)\times n+j}=A_i$. The $i$-th equation of the second type is $\sum_{j=1}^n a_{i+(j-1)\times n}=B_i$. But this is too easy. You are also given $m$ constraints, and you need to ensure $a_{p_i}=q_i$. Please output any valid solution. If there is no solution, output `No Solution`. Otherwise, first output `OK`, then output the solution, where for all $\forall i\in[1,n^2]$, $a_i \in[-2^{63},2^{63})$ and is an integer.

**This problem contains multiple test cases.** The first line contains an integer $T$, the number of test cases. For each test case: The first line contains two integers $n$ and $m$. The second line contains $n$ integers, where the $i$-th integer represents $A_i$. The third line contains $n$ integers, where the $i$-th integer represents $B_i$. Then follow $m$ lines, each with two integers, representing $p_i, q_i$.

For each test case: The first line contains a string indicating whether a solution exists. If a solution exists, the next line contains $n \times n$ integers, where the $i$-th integer represents $a_i$.

**This problem uses bundled testdata.** - Subtask 1 (1 pts): $n=1$. - Subtask 2 (4 pts): $n\le 3$. - Subtask 3 (10 pts): $n\le 10$. - Subtask 4 (15 pts): $n\le 100$. - Subtask 5 (20 pts): $m\le n-1$. - Subtask 6 (10 pts): $m=0$. - Subtask 7 (20 pts): $T\le 10$, $n\le 500$. - Subtask 8 (20 pts): no special constraints. For $100\%$ of the testdata, $1\le T\le 10^5$, $1\le n \le 2000$, $1\le \sum n^2\le 4\times 10^6$, $-5\times 10^{12}\le A_i,B_i\le 5\times 10^{12}$, $0\le m\le n^2$, $1\le p_i\le n^2$, $-10^9\le q_i\le 10^9$. It is guaranteed that all $p_i$ are pairwise distinct. Translated by ChatGPT 5