AT_arc222_c.2 Directions vs 4 Directions

There is an $N\times N$ grid, where $N$ is an integer at least $2$. For $1\leq i,j\leq N$, the cell at row $i$ from the top and column $j$ from the left is denoted by $(i,j)$.

Initially, all cells are black. For each cell $(i,j)$, a cost $A_{i,j}$ to change the color of the cell from black to white is given.

Alice and Bob play a game using this grid and one piece. The game consists of the following three steps.

Step 1

The referee specifies the cell where the piece is initially placed.

Step 2

Alice performs the following operation zero or more times:

• Choose a black cell $(i,j)$, pay cost $A_{i,j}$, and change that cell to white.

Step 3

Place the piece on the cell specified as the initial position in Step 1. Then, starting with Alice, Alice and Bob take turns making moves.

• On Alice's turn, Alice moves the piece to an adjacent cell to the left or right.
• On Bob's turn, Bob moves the piece to an adjacent cell in any of the up, down, left, or right directions.

A move that would take the piece outside the grid is not allowed.

Step 3 ends immediately after Alice and Bob have each taken $10^{10}$ turns.

At the end of Step 3, if the piece is on a white cell, Alice wins; if it is on a black cell, Bob wins. In Step 3, Alice and Bob each act optimally to win.

For each cell $(h,w)$, find the minimum total cost that Alice must pay in Step 2 to guarantee a win if $(h,w)$ is specified as the initial cell in Step 1.

$T$ test cases are given; solve each of them.

存在一个 $N\times N$ 的网格，其中 $N$ 是一个不小于 $2$ 的整数。对于 $1\leq i,j\leq N$，从上往下第 $i$ 行、从左往右第 $j$ 列的格子记为 $(i,j)$。

初始时，所有格子均为黑色。对每个格子 $(i,j)$，给定将其颜色由黑变为白的代价 $A_{i,j}$。

Alice 和 Bob 使用该网格及一枚棋子进行一场游戏。游戏包含以下三个步骤：

步骤 1

裁判指定棋子初始放置的位置。

步骤 2

Alice 可执行零次或多次如下操作：

• 选择一个黑色格子 $(i,j)$，支付代价 $A_{i,j}$，并将该格子变为白色。

步骤 3

将棋子置于步骤 1 中指定的初始位置。随后，从 Alice 开始，Alice 和 Bob 轮流移动棋子，共进行 $10^{10}$ 轮（即每人各走 $10^{10}$ 步）。

• 在 Alice 的回合中，她只能将棋子向左或右的相邻格子移动；
• 在 Bob 的回合中，他可将棋子向上、下、左、右四个方向之一的相邻格子移动。

不允许将棋子移出网格边界。

步骤 3 在 Alice 和 Bob 各完成 $10^{10}$ 次移动后立即结束。

步骤 3 结束时，若棋子位于白色格子，则 Alice 获胜；若位于黑色格子，则 Bob 获胜。在步骤 3 中，Alice 和 Bob 均采取最优策略以争取获胜。

对每个格子 $(h,w)$，求 Alice 在步骤 2 中需支付的最小总代价，使得当 $(h,w)$ 被指定为步骤 1 中的初始位置时，Alice 必胜。

共给出 $T$ 组测试数据，请分别求解。

The input is given from Standard Input in the following format:

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

Each test case is given in the following format:

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

输入从标准输入中按以下格式给出：

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

每个测试用例按以下格式给出：

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

Output $N$ lines per test case.

For each test case, the $h$-th line should contain the minimum total cost that Alice must pay in Step 2 to guarantee a win for each of $(h,1),(h,2),\ldots,(h,N)$ specified as the initial cell, space-separated.

每个测试用例输出 $N$ 行。

对于每个测试用例，第 $h$ 行应包含：当初始格子分别为 $(h,1),(h,2),\ldots,(h,N)$ 时，Alice 在步骤 2 中为确保获胜所需支付的最小总费用（以空格分隔）。

Sample 1 Explanation:
Let us explain the first test case.

For $(h,w) = (1,1)$ or $(h,w) = (2,2)$, Alice changes cells $(1,1)$ and $(2,2)$ to white.

In this case, at the end of each of Bob's turns, the piece is at $(1,1)$ or $(2,2)$. Therefore, immediately after Alice and Bob have each taken $10^{10}$ turns, the piece is at $(1,1)$ or $(2,2)$, so Alice wins regardless of how the piece is moved. The cost Alice pays in Step 2 is $A_{1,1}+A_{2,2}=1+2=3$.

For $(h,w) = (1,2)$ or $(h,w) = (2,1)$, it can be verified that Alice can win by changing cells $(1,2)$ and $(2,1)$ to white. In this case, the cost Alice pays in Step 2 is $A_{1,2}+A_{2,1}=4+3=7$.

Constraints

• $1\leq T\leq 10^4$
• $2\leq N\leq 500$
• $0\leq A_{i,j}\leq 10^9$
• All input values are integers.
• The sum of $N^2$ over all test cases is at most $500^2$.

样例 1 解释：
我们来解释第一个测试用例。

当 $(h,w) = (1,1)$ 或 $(h,w) = (2,2)$ 时，Alice 将格子 $(1,1)$ 和 $(2,2)$ 变为白色。

此时，在 Bob 每一轮操作结束时，棋子均位于 $(1,1)$ 或 $(2,2)$。因此，在 Alice 和 Bob 各自进行了 $10^{10}$ 轮操作后，棋子必然处于 $(1,1)$ 或 $(2,2)$，故无论棋子如何移动，Alice 均获胜。Alice 在第 2 步中付出的代价为 $A_{1,1}+A_{2,2}=1+2=3$。

当 $(h,w) = (1,2)$ 或 $(h,w) = (2,1)$ 时，可以验证 Alice 通过将格子 $(1,2)$ 和 $(2,1)$ 变为白色即可获胜。此时，Alice 在第 2 步中付出的代价为 $A_{1,2}+A_{2,1}=4+3=7$。

约束条件

• $1\leq T\leq 10^4$
• $2\leq N\leq 500$
• $0\leq A_{i,j}\leq 10^9$
• 所有输入值均为整数。
• 所有测试用例中 $N^2$ 的总和不超过 $500^2$。