Xưởng vẽ

Một xưởng vẽ có $n$ họa sĩ cùng làm ra $m$ bức tranh. Mỗi họa sĩ dùng đúng một màu riêng của mình, và mỗi bức tranh đều phải được tô lần lượt bởi cả $n$ màu.

Quy trình làm việc tuân theo các quy tắc sau:

• Mỗi bức tranh được tô lần lượt bởi họa sĩ $1$, rồi họa sĩ $2$, ..., đến họa sĩ $n$. Sau khi họa sĩ thứ $j$ tô xong bức tranh, bức tranh chuyển ngay cho họa sĩ thứ $j+1$ (nếu $j<n$).
• Mỗi họa sĩ xử lý các bức tranh theo thứ tự: trước tiên bức tranh $1$, rồi bức tranh $2$, ..., đến bức tranh $m$.
• Tại mỗi thời điểm, một họa sĩ chỉ tô được một bức tranh. Họa sĩ không cần nghỉ: ngay khi tô xong một bức, họ bắt đầu bức tiếp theo (nếu đã có sẵn).
• Ngay khi họa sĩ thứ $j$ tô xong phần của mình trên một bức tranh, bức tranh đó lập tức sẵn sàng cho họa sĩ tiếp theo.

Họa sĩ thứ $j$ cần $t_{ij}$ đơn vị thời gian để tô màu của mình lên bức tranh thứ $i$. Tất cả các họa sĩ bắt đầu làm việc tại thời điểm $0$.

Với mỗi bức tranh, hãy tìm thời điểm nó hoàn thành, tức thời điểm họa sĩ thứ $n$ tô xong bức tranh đó.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $m$ và $n$: số bức tranh và số họa sĩ.
• $m$ dòng tiếp theo, dòng thứ $i$ chứa $n$ số nguyên $t_{i1},t_{i2},\dots ,t_{in}$: thời gian họa sĩ thứ $j$ cần để tô bức tranh thứ $i$.

Dữ liệu ra

In ra $m$ số nguyên $r_1,r_2,\dots ,r_m$ trên một dòng, trong đó $r_i$ là thời điểm bức tranh thứ $i$ được hoàn thành.

Ràng buộc

• $1\le m\le 50000$
• $1\le n\le 5$
• $1\le t_{ij}\le 1000$

Ví dụ