Problem Description

The free space in Mr. X's office is equipped with massage chairs arranged in $ N $ rows and $ N $ columns.
The coordinates of the massage chair at the $ i $th row from the top and the $ j $th column from the left are denoted as $(i,\ j)$.

The massage chairs have various performances.
The performance of the massage chair at $(i,\ j)$ is represented by an integer between $ 1 $ and $ 30 $, denoted as $E_{i,\ j}$, with higher values indicating better performance.
Additionally, the power to move the massage chair at $(i,\ j)$ can be set freely as an integer between $ 0 $ and $ N $, denoted as $P_{i,\ j}$.

• A massage chair with power set to $ 0 $ is not used and no one will sit on it.
• A massage chair with power set to non-zero will always have someone sit on it.
• When moving the massage chair at $(i,\ j)$ with non-zero power $P_{i,\ j}$, the power will produce noise that can be heard around it, so other massage chairs within a Manhattan distance of $P_{i,\ j}$ from $(i,\ j)$ must be set to power $ 0 $ to ensure no one sits on them.

The following image is an example of setting non-zero power to some massage chairs. The integers written in the squares represent the power assigned to the massage chair at that position, and the pink squares indicate positions where the massage chairs must not be used.

After Mr. X decides the power settings for each massage chair, people will sit on all massage chairs with non-zero power.
The person sitting on the massage chair at $(i,\ j)$ will gain a satisfaction score of $E_{i,j} \times P_{i,j}$.
Maximize the sum of the satisfaction scores gained by the people sitting on the massage chairs.

The score for each test case and the total score for this problem are calculated as follows:

• For a single test case, the sum of the satisfaction scores gained by the people sitting on the massage chairs is directly the score.
• There are a total of $ 50 $ test cases. The sum of the scores for all test cases is the score for this problem.

Input Format

The input is given from the standard input in the following format:
The first line contains a single integer $ N $. The following $ N $ lines each contain $ N $ integers separated by spaces.

```

\(\begin{array}{lll}
    N & & \\
    E_{ 0,0 } & \ldots & E_{ 0,N-1 } \\
    \vdots & \ddots & \vdots \\
    E_{ N-1,0 } & \ldots & E_{ N-1,N-1 }
  \end{array}\)


- $ N $ is an integer representing the number of rows and columns of massage chairs, satisfying $ N = 40 $.
- $ E_{i,j} $ is an integer representing the **performance** of the massage chair at $(i,\ j)$, satisfying $1 \leq E_{i,j} \leq 30$.

## Output Format

The output consists of $ N $ lines, each containing $ N $ integers separated by spaces, printed to the standard output.

 ```
<pre style="font-family: Menlo,Monaco,Consolas,'Courier New',monospace; font-size: 13px;">
\(\begin{array}{lll}
    P_{ 0,0 } & \ldots & P_{ 0,N-1 } \\
    \vdots & \ddots & \vdots \\
    P_{ N-1,0 } & \ldots & P_{ N-1,N-1 }
  \end{array}\)



- $ P_{i,j} $ is an integer representing the **power** to move the massage chair at $(i,\ j)$, satisfying $0 \leq P_{i,j} \leq N$.
- Massage chairs affected by the noise must be set to **power** $ 0 $.
- The output will result in a WA if it does not satisfy the above constraints.

## Sample Input and Output

### Sample Input #1


4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16



### Sample Output #1


0 1 0 0
1 0 0 0
0 0 0 0
0 0 0 4



### Sample Input #2

```
40
4 2 1 1 1 1 3 1 1 1 6 1 1 2 1 1 6 17 3 5 1 2 5 2 1 1 1 1 6 12 1 4 1 3 1 1 2 1 3 2
1 1 4 1 1 4 1 1 1 12 3 1 1 1 1 7 1 1 2 1 3 1 11 1 1 1 1 1 1 1 1 1 1 2 1 1 2 4 6 3
5 6 1 1 2 1 3 4 5 1 9 1 1 2 26 6 3 1 1 1 2 4 1 2 1 1 3 1 3 1 1 2 1 1 6 1 2 1 2 1
1 1 1 16 1 1 10 1 1 1 3 7 1 1 1 1 1 2 1 1 1 1 1 19 1 1 2 3 6 1 2 12 1 2 4 1 1 1 1 1
1 1 1 1 1 1 3 1 1 1 2 1 1 1 1 9 1 1 1 8 2 2 2 1 1 2

见题面 Input 部分

见题面 Output 部分