You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

现有 $n$ 个画家（编号从 $1$ 到 $n$）去完成 $m$ （编号从 $1$ 到 $m$）幅画，画画的规则是：

1. 每个画家都需要在每幅画上作画
2. 对于第i号画家，他作画j幅画的条件为:[1,i-1]的所有画家在j幅画上作画完成，同时第i号画家完成[1,j-1]之间所有的作画

从 $0$ 时刻开始，求每幅画完成的最早时刻是多少？

Input Format

第一行包含两个正整数 $m,n$ ( $1\le m\le 5\times 10^4,1\le n\le 5$ ）;

接下来的 $m$ 行，每行包含 $n$ 个数 $t_{i1},t_{i2},...,t_{in}$ ( $1\le t_{ij}\le 1000$ )，这里 $t_{ij}$ 表示第 $j$ 个画家需要在第 $i$ 幅画上画画的时间。

Output Format

仅有一行，包含 $m$ 个正整数 $r_{1},r_{2},...,r_{m}$ ，这里 $r_{i}$ 表示第 i 幅画全部完成的时间。各数两两之间用一个空格分隔。

5 1
1
2
3
4
5

1 3 6 10 15 

4 2
2 5
3 1
5 3
10 1

7 8 13 21 

Hint

数据范围：

​ 对于 $10\%$ 的数据 $m \le 100,n=1$； ​ 对另外 $20\%$ 的数据 $m \le 100,n=2$； ​ 对于另外的 $70\%$ 数据 $m \le 50000,n\le 5$ 。

Note

对于样例2的解释：

所以，答案是7 8 13 21