CF416B.Art Union

A well-known art union called "Kalevich is Alive!" manufactures objects d'art (pictures). The union consists of n painters who decided to organize their work as follows.

Each painter uses only the color that was assigned to him. The colors are distinct for all painters. Let's assume that the first painter uses color 1, the second one uses color 2, and so on. Each picture will contain all these n colors. Adding the j-th color to the i-th picture takes the j-th painter t__ij units of time.

Order is important everywhere, so the painters' work is ordered by the following rules:

• Each picture is first painted by the first painter, then by the second one, and so on. That is, after the j-th painter finishes working on the picture, it must go to the (j + 1)-th painter (if j < n);
• each painter works on the pictures in some order: first, he paints the first picture, then he paints the second picture and so on;
• each painter can simultaneously work on at most one picture. However, the painters don't need any time to have a rest;
• as soon as the j-th painter finishes his part of working on the picture, the picture immediately becomes available to the next painter.

Given that the painters start working at time 0, find for each picture the time when it is ready for sale.

一个名为“卡拉维奇永存！”（Kalevich is Alive!）的著名艺术联合会专门制作艺术品（画作）。该联合会由 $n$ 位画家组成，他们决定按如下方式组织工作：

每位画家仅使用分配给自己的颜色，且所有画家的颜色互不相同。假设第一位画家使用颜色 $1$，第二位画家使用颜色 $2$，依此类推。每幅画作都将包含全部 $n$ 种颜色。第 $j$ 位画家为第 $i$ 幅画作添加第 $j$ 种颜色所需的时间为 $t_{ij}$。

秩序在任何地方都至关重要，因此画家们的工作遵循以下规则：

• 每幅画作首先由第一位画家绘制，然后由第二位画家绘制，依此类推。即：第 $j$ 位画家完成对某幅画作的工作后，该画作必须立即交给第 $(j+1)$ 位画家（若 $j < n$）；
• 每位画家按某种固定顺序处理画作：他先绘制第一幅画作，再绘制第二幅画作，依此类推；
• 每位画家同一时刻最多只能处理一幅画作。但画家无需任何休息时间；
• 第 $j$ 位画家一旦完成对某幅画作的绘制工作，该画作便立即可供下一位画家使用。

已知所有画家均于时刻 $0$ 开始工作，请对每幅画作，求出其完成并可上市销售的时刻。

The first line of the input contains integers m, n (1 ≤ m ≤ 50000, 1 ≤ n ≤ 5), where m is the number of pictures and n is the number of painters. Then follow the descriptions of the pictures, one per line. Each line contains n integers _t__i_1, _t__i_2, ..., t__in (1 ≤ t__ij ≤ 1000), where t__ij is the time the j-th painter needs to work on the i-th picture.

输入的第一行包含两个整数 $m$ 和 $n$（$1 \leq m \leq 50000$，$1 \leq n \leq 5$），其中 $m$ 表示画作的数量，$n$ 表示画家的数量。随后是每幅画作的描述，每行一幅。每行包含 $n$ 个整数 $t_{i1},\,t_{i2},\,\dots,\,t_{in}$（$1 \leq t_{ij} \leq 1000$），其中 $t_{ij}$ 表示第 $j$ 位画家完成第 $i$ 幅画作所需的时间。

Print the sequence of m integers _r_1, _r_2, ..., r__m, where r__i is the moment when the n-th painter stopped working on the i-th picture.

输出长度为 $m$ 的整数序列 $r_1,\,r_2,\,...,\,r_m$，其中 $r_i$ 表示第 $n$ 位画家完成第 $i$ 幅画作的时刻。