#P13109. [AGC064E] Cross Sum Construction

[AGC064E] Cross Sum Construction

题目描述

给定一个正整数 NN 和两个长度为 NN 的整数序列 A=(a1,…,aN), B=(b1,…,bN)A=(a_1,\ldots,a_N),\ B=(b_1,\ldots,b_N)。
另外,定义多重集合 XX,其包含 N2N^2 个值 (ai+bj) (1≤i,j≤N)(a_i+b_j)\ (1\leq i,j\leq N)。

对于每个元素都在 [−1018, 1018][-10^{18},\ 10^{18}] 范围内的 N×NN\times N 整数矩阵 MM,定义其分数如下:

  • 设 SS 为一个多重集合,包含 N2N^2 个值,分别为“MM 的第 ii 行或第 jj 列中属于的 2N−12N-1 个元素的总和”(1≤i,j≤N)(1\leq i,j\leq N)。此时,分数为对所有整数 zz,min⁡(\min(XX 中 zz 的出现次数, SS 中 zz 的出现次数)) 的总和。

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

TT 组测试数据,请分别解决上述问题。

输入格式

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

TT
test1\mathrm{test}_1
⋮\vdots
testT\mathrm{test}_T

每个测试用例格式如下:

NN
a1 a2 … aNa_1\ a_2\ \ldots\ a_N
b1 b2 … bNb_1\ b_2\ \ldots\ b_N

输出格式

对于每个测试用例,输出如下格式:

m1,1 m1,2 … m1,Nm_{1,1}\ m_{1,2}\ \ldots\ m_{1,N}
⋮\vdots
mN,1 mN,2 … mN,Nm_{N,1}\ m_{N,2}\ \ldots\ m_{N,N}

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

输入输出样例 #1

输入 #1

3
1
5
-10
2
0 -1
8 -11
3
20 23 26
1 2 3

输出 #1

-5
8 9
-10 -9
2 9 4
7 5 3
6 1 8

说明/提示

限制条件

  • 1≤T≤2.5×1051\leq T\leq 2.5\times 10^5
  • 1≤N≤5001\leq N\leq 500
  • −109≤ai,bi≤109-10^9\leq a_i,b_i\leq 10^9
  • 所有测试用例中 N2N^2 的总和不超过 2.5×1052.5\times 10^5
  • 输入均为整数

样例说明 1

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