Sean's Swathers 制造定制割晒机（用于收割谷物的设备）。所有割晒机在建造过程中都要经过相同的基本阶段：例如，它们都需要安装割刀、输送带和拨禾轮。然而，这些部件可以根据买家的需求进行定制，因此不同割晒机的各个阶段可能需要不同的时间。

已订购了 $N$ 台割晒机，制造过程中有 $M$ 个阶段。每台割晒机都将按照相同的阶段顺序进行加工。

具体来说，加工过程如下：对于每台割晒机 $i$ 和每个阶段 $j$，割晒机 $i$ 在阶段 $j$ 需要花费 $P_{i,j}$ 个单位的时间来完成。每个阶段的工人一次只能加工一台割晒机。在一天开始时，所有割晒机订单都已准备好由第一阶段进行加工。在加工过程中的任何时刻，如果阶段 $j$ 的工人处于空闲状态，并且有割晒机在该阶段等待加工，则工人将选择编号最小的割晒机（割晒机的编号为 $1$ 到 $N$）。请注意，只有在阶段 $j - 1$ 的工作完成后，才能开始阶段 $j$ 的工作。

确定每台割晒机完工的时间。

输入格式

每个文件中只有一个测试用例。第一行包含两个整数 $N$ 和 $M$（$1 \le N, M \le 1000$），分别表示割晒机的数量和阶段的数量。

接下来有 $N$ 行，每行包含 $M$ 个整数。第 $i$ 行的第 $j$ 个整数为 $P_{i,j}$，表示阶段 $j$ 的工人完成割晒机 $i$ 所需的时间（$1 \le P_{i,j} \le 10^6$）。

输出格式

输出单行，包含 $N$ 个整数 $T_1\ T_2\ \dots\ T_n$，每两个相邻整数之间用单个空格分隔。其中 $T_i$ 表示割晒机 $i$ 在阶段 $M$ 完工的时间。

样例

输入样例 1

2 3
1 2 3
3 2 1

输出样例 1

6 7

输入样例 2

3 2
3 1
4 7
2 5

输出样例 2

4 14 19