AT_agc064_e.[AGC064E] Cross Sum Construction

给定一个正整数 $N$ 和两个长度为 $N$ 的整数序列 $A=(a_1,\ldots,a_N),\ B=(b_1,\ldots,b_N)$。
另外，定义多重集合 $X$，其包含 $N^2$ 个值 $(a_i+b_j)\ (1\leq i,j\leq N)$。

对于每个元素都在 $[-10^{18},\ 10^{18}]$ 范围内的 $N\times N$ 整数矩阵 $M$，定义其分数如下：

• 设 $S$ 为一个多重集合，包含 $N^2$ 个值，分别为“$M$ 的第 $i$ 行或第 $j$ 列中属于的 $2N-1$ 个元素的总和”$(1\leq i,j\leq N)$。此时，分数为对所有整数 $z$，$\min($ $X$ 中 $z$ 的出现次数，$S$ 中 $z$ 的出现次数 $)$ 的总和。

请你对于每个测试用例，求出一个能使分数最大的矩阵 $M$。

$T$ 组测试数据，请分别解决上述问题。

输入以如下格式从标准输入给出，其中 $\mathrm{test}_i$ 表示第 $i$ 个测试用例。

$T$
$\mathrm{test}_1$
$\vdots$
$\mathrm{test}_T$

每个测试用例格式如下：

$N$
$a_1\ a_2\ \ldots\ a_N$
$b_1\ b_2\ \ldots\ b_N$

对于每个测试用例，输出如下格式：

$m_{1,1}\ m_{1,2}\ \ldots\ m_{1,N}$
$\vdots$
$m_{N,1}\ m_{N,2}\ \ldots\ m_{N,N}$

其中，$m_{i,j}$ 表示分数最大的矩阵 $M$ 的第 $i$ 行第 $j$ 列的元素，且需满足 $-10^{18}\leq m_{i,j}\leq 10^{18}$。
若存在多个分数最大的矩阵 $M$，输出其中任意一个均可。

限制条件

• $1\leq T\leq 2.5\times 10^5$
• $1\leq N\leq 500$
• $-10^9\leq a_i,b_i\leq 10^9$
• 所有测试用例中 $N^2$ 的总和不超过 $2.5\times 10^5$
• 输入均为整数

样例说明 1

第 $1$ 个测试用例中，$X=\{-5\},\ S=\{-5\}$，分数为 $1$。
第 $2$ 个测试用例中，$X=\{8,-11,7,-12\},\ S=\{7,8,-11,-10\}$，分数为 $3$。
第 $3$ 个测试用例中，$X=\{21,22,23,24,25,26,27,28,29\},\ S=\{28,21,26,23,25,27,24,29,22\}$，分数为 $9$。

由 ChatGPT 4.1 翻译