题目描述

给出一个 $n$，现在有 $n\times n$ 个未知数 $a_{1},a_{2},\cdots,a_{n\times n}$。

给出 $2\times n$ 个方程，方程共有两种，每种分别有 $n$ 个。

第一种方程的 $i$ 个方程为 $\sum_{j=1}^na_{(i-1)\times n+j}=A_i$。
第二种方程的 $i$ 个方程为 $\sum_{j=1}^na_{i+(j-1)\times n}=B_i$。

可这太简单了，给出 $m$ 个限制，你需要保证 $a_{p_i}=q_i$。

请求出任意一组合法的解。无解输出 No Solution，否则先输出 OK，接着给出解，其中 $\forall i\in[1,n^2]$，$a_i \in[-2^{63},2^{63})$ 且是个整数。

输入格式

本题多组数据。

第一行一个整数 $T$，表示数据组数。
对于每组数据：
第一行两个整数 $n$ 和 $m$。
第二行 $n$ 个整数，第 $i$ 个整数表示 $A_i$。
第三行 $n$ 个整数，第 $i$ 个整数表示 $B_i$。
接下来 $m$ 行，每行两个整数，表示 $p_i,q_i$。

输出格式

对于每组数据：
第一行一个字符串，表示是否有解。
如果有解，接下来一行 $n\times n$ 个整数，第 $i$ 个整数表示 $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

提示

本题采用捆绑测试。

• Subtask1（1pts）：$n=1$；
• Subtask2（4pts）：$n\le3$；
• Subtask3（10pts）：$n\le 10$；
• Subtask4（15pts）：$n\le 100$；
• Subtask5（20pts）：$m\le n-1$；
• Subtask6（10pts）：$m=0$；
• Subtask7（20pts）：$T\le 10$，$n\le 500$；
• Subtask8（20pts）：无特殊限制。

对于 $100\%$ 的数据，$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$。保证 $p_i$ 互不相同。