Problem D
Flow Shop

Photo by ken figlioli cc by-sa 2.0

$N$ swathers have been ordered and there are $M$ stages in the manufacturing process. The swathers will each go through the same sequence of stages.

In particular, the processing occurs as follows: For each swather $i$ and each stage $j$, it takes $P_{i,j}$ units of time to complete stage $j$ for swather $i$. The workers at each stage may only work on one swather at a time. At the start of the day all swather orders are ready to be processed by the first stage. At any point in the process, if the workers at stage $j$ are idle and there are swathers waiting to be processed at this stage then the workers will pick the swather that has the lowest label (they are labelled from $1$ to $N$). Note that the work on a stage $j$ can only be started after the work on the stage $j-1$ is completed.

Determine the time each swather is completed.

Input

There is only one test case in each file. It begins with a single line containing $N$ and $M$ ($1 \leq N,M \leq 1000$), the number of swathers and stages (respectively). Following this are $N$ lines, each with $M$ integers. The $j$’th integer of the $i$’th line is $P_{i,j}$, giving the amount of time it will take for the workers at stage $j$ to complete swather $i$ ($1 \leq P_{i,j} \leq 10^6$).

Output

Output a single line containing $N$ integers $T_1~ T_2~ \ldots ~ T_ n$ with a single space between consecutive integers. These should be such that stage $M$ for swather $i$ is completed at time $T_ i$.

2 3
1 2 3
3 2 1

6 7

3 2
3 1
4 7
2 5

4 14 19