AT_agc064_e [AGC064E] Cross Sum Construction

[problemUrl]: https://atcoder.jp/contests/agc064/tasks/agc064_e 正整数 $ 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 $ を $ 1 $ つ求めてください。 $ T $ ケースについて上記問題を解いてください。

入力は以下の形式で標準入力から与えられる。ここで、$ \mathrm{test}_i $ は $ i $ 番目のテストケースを表す。 > $ T $ $ \mathrm{test}_1 $ $ \vdots $ $ \mathrm{test}_T $ 各テストケースは以下の形式で与えられる。 > $ N $ $ a_1 $ $ \ldots $ $ a_N $ $ b_1 $ $ \ldots $ $ b_N $

各テストケースについて、以下の形式で出力せよ。 > $ m_{1,1} $ $ \ldots $ $ m_{1,N} $ $ \vdots $ $ m_{N,1} $ $ \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 $ - $ 1 $ つの入力に含まれるテストケースについて、$ N^2 $ の総和は $ 2.5\ \times\ 10^5 $ 以下 - 入力はすべて整数 ### Sample Explanation 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 $ です。