{"raw_statement":[{"iden":"problem statement","content":"You are given a positive integer $N$ and integer sequences of length $N$: $A=(a_1,\\ldots,a_N)$ and $B=(b_1,\\ldots,b_N)$.  \nLet $X$ be the multiset of $N^2$ instances $(a_i+b_j)(1 \\leq i,j \\leq N)$.\nFor an $N \\times N$ matrix $M$ whose elements are integers between $-10^{18}$ and $10^{18}$, inclusive, we define the score as follows.\n\n*   Let $S$ be the multiset of $N^2$ instances, each of which is the sum of the $2N-1$ elements in the $i$\\-th row or $j$\\-th column of $M$ $(1 \\leq i,j \\leq N)$. Then, the score is the sum of $\\min($the multiplicity of $z$ in $X$, the multiplicity of $z$ in $S)$ over all integers $z$.\n\nFind a matrix $M$ with the maximum score.\nSolve the above problem for $T$ cases."},{"iden":"constraints","content":"*   $1 \\leq T \\leq 2.5 \\times 10^5$\n*   $1 \\leq N \\leq 500$\n*   $-10^9 \\leq a_i,b_i \\leq 10^9$\n*   The sum of $N^2$ over the test cases in a single input is at most $2.5 \\times 10^5$.\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format, where $\\mathrm{test}_i$ represents the $i$\\-th test case:\n\n$T$\n$\\mathrm{test}_1$\n$\\vdots$\n$\\mathrm{test}_T$\n\nEach test case is given in the following format:\n\n$N$\n$a_1$ $\\ldots$ $a_N$\n$b_1$ $\\ldots$ $b_N$"},{"iden":"sample input 1","content":"3\n1\n5\n-10\n2\n0 -1\n8 -11\n3\n20 23 26\n1 2 3"},{"iden":"sample output 1","content":"\\-5\n8 9\n-10 -9\n2 9 4\n7 5 3\n6 1 8\n\nFor the input and output in the first case, $X={-5}, S={-5}$, for a score of $1$.  \nFor the input and output in the second case, $X={8,-11,7,-12}, S={7,8,-11,-10}$, for a score of $3$.  \nFor the input and output in the third case, $X={21,22,23,24,25,26,27,28,29}, S={28,21,26,23,25,27,24,29,22}$, for a score of $9$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}