Code Submission Evaluation System Login

KILO 2018 4/5

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

Tasks | Scoreboard | Statistics


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: 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
Example

Input:
2
1 4
2 3

Output:
0 2 2 1 0