Description

现有 $n$ 个画家（编号从 $1$ 到 $n$）去完成 $m$ （编号从 $1$ 到 $m$）幅画，画画的规则是：每个画家都需要在每幅画上画画，必须严格按照每幅画的编号从小到大逐一完成；每幅画都需要 $n$ 个画家来共同完成，必须编号小的画家完成之后编号大的画家才能开始。从 $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$ 。