Problem Description

Takahashi took the same exam $ T $ times. Each exam consists of $ N $ subjects numbered from $ 1 $ to $ N $.
Takahashi scored $ P_{i,j} $ points in subject $ j $ in the $ i $-th exam.

For each $K=1,2,\ldots,T$, answer the following question:

Question:
Let $ C_j $ be the highest score in subject $ j $ among the results of the first $ K $ exams (including the $ K $-th exam). Find $C_1+\ldots+C_N$.

Input Format

The input is given from the standard input in the following format:

$ T $ $ N $ $ P_{1,1} $ $ P_{1,2} $ $\ldots$ $ P_{1,N} $ $\vdots$ $ P_{T,1} $ $ P_{T,2} $ $\ldots$ $ P_{T,N} $

Output Format

Output $ T $ lines. The $ i $-th line should contain the answer for $ K=i $.

Sample Input and Output

Sample Input #1

2 3
50 80 60
60 70 70

Sample Output #1

190
210

Sample Input #2

4 4
1 2 3 4
2 3 4 1
4 1 2 3
3 4 1 2

Sample Output #2

10
13
15
16

Notes/Hints

Constraints

• $1 \leq T \leq 10^3$
• $1 \leq N \leq 10$
• $0 \leq P_{i,j} \leq 10^5$
• All values included in the input are integers.

Sample Explanation 1

Takahashi scored $ 50, 80, 60 $ points in each subject in the first exam, and $ 60, 70, 70 $ points in the second exam. - The answer for $ K=1 $ is $ 50+80+60=190 $. - The answer for $ K=2 $ is $ 60+80+70=210 $.

见题面 Input 部分

见题面 Output 部分