Grid Number Picking (k Paths)

Problem Description

You are given an $n \times n$ matrix where each cell holds a non-negative integer $A_{i, j}$. Starting from $(1, 1)$ you may move only right or down to reach $(n, n)$; upon reaching a cell you take its number and that cell's value becomes $0$. You repeat this walk $k$ times. For each $k = 1, 2, \dots, n$, find the maximum possible sum of the numbers taken over $k$ walks.

Input Format

The first line contains one integer $n\ (1 \le n \le 50)$.

The next $n$ lines each contain $n$ integers, the values $A_{i, j}\ (1 \le A_{i, j} \le 1000)$ of the matrix cells.

Output Format

Output $n$ lines, the answer for $k = 1, 2, \dots, n$ in order.

Sample Input

3
1 2 3
0 2 1
1 4 2

Sample Output

11
15
16