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