Problem Description

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.

Input Format

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$.

Output Format

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$.

1
5 17
8 10 12 8 45
16 17 18 18 14
3 2
4 3
6 3
7 2
8 2
10 2
11 2
12 4
13 2
14 3
18 3
19 2
21 9
22 9
23 9
24 9
25 9

OK
1 1 2 3 1 3 2 2 1 2 2 4 2 3 1 1 1 3 2 1 9 9 9 9 9

Hint

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