KILO 2018 4/5

 Start: 2018-09-27 16:30:00 End: 2018-09-27 18:30:00

CSES - KILO 2018 4/5 - HabitatCSES - Habitat

Habitat

 Time limit: 1.00 s Memory limit: 512 MB

Uolevi has gotten a new job at a wildlife reserve.

The reserve can be represented as an $n \times n$ rectangle. Every position $(x, y)$ has a humidity bound $b_{(x, y)}$. We call a position $(x, y)$ muddy if:
• $b_{(x, y)} > k$
• There exists a position $(x_{\#}, y_{\#})$, such that $b_{(x_{\#}, y_{\#})} \leq k$, and $\left|x - x_{\#}\right| + \left|y - y_{\#}\right| \leq k$
where $k$ is the humidity constant for the reserve.

Uolevi's first task is to calculate the amount of habitable area for hippoes at the park. Since hippoes like mud, this is equal to the amount of muddy positions. However, he doesn't know the humidity constant for the reserve.

Can you calculate the amount of muddy positions for every humidity constant $k \in [0, n^{2}]$. Can you help him with this task?

Input

The first line of input contains the integer $n$: The size of the reserve.

After this, $n$ lines follow, each containing $n$ integers. The $x$'th integer on the $y$'th line is $b_{(x, y)}$.

Output

Output the number of muddy positions $(x, y)$ for every $k \in [0, n^{2}]$

Constraints
• $1 \leq n \leq 100$
• $1 \leq b_{(x, y)} \leq n^{2}$
Example

Input: 2 1 4 2 3 
Output: 0 2 2 1 0