一个名为“Kalevich is Alive!”的知名艺术联盟生产艺术品(图片)。该工会由 n 位画家组成,他们决定按如下方式组织他们的工作。
每个画家仅使用分配给他的颜色。所有画家的颜色都是不同的。我们假设第一个画家使用颜色 1,第二个画家使用颜色 2,依此类推。每张图片将包含所有这n种颜色。将第 j 个颜色添加到第 i 张图片需要第 j 个画家 tij 单位的时间。
顺序在任何地方都很重要,因此画家的作品按以下规则排序:
- 每幅画首先由第一个画家绘制,然后由第二个画家绘制,依此类推。即第j个画家完成图片工作后,必须转到第(j + 1)个画家(如果j < n);
- 每个画家按某种顺序处理图片:首先,他画第一幅画,然后画第二幅画,依此类推;
- 每个画家最多可以同时处理一张图片。然而,画家们不需要任何时间休息,他们需要时间来休息。
- 一旦第 j 个画家完成了他在图片上的工作,该图片就立即可供下一个画家使用。
鉴于画家在时间 0 开始工作,找出每幅画准备出售的时间。
输入
输入的第一行包含整数 m, n (1 ≤ m ≤ 50000, 1 ≤ n ≤ 5),其中 m 是图片数量,n 是画家数量。然后按照图片的描述进行操作,每行一张。每行包含 n 个整数 ti1, ti2, ...,tin (1 ≤ tij ≤ 1000),其中 tij 是第 j 个画家处理第 i 张图片所需的时间。
输出
打印 m 个整数 r1, r2, ..., rm 的序列,其中 ri 是第 n 个画家停止绘制第 i 张图片的时刻。
示例
输入 #1
5 1 1 2 3 4 5
输出 #1
1 3 6 10 15
输入 #2
4 2 2 5 3 1 5 3 10 1
输出 #2
7 8 13 21