32829번 - Bottles 다국어

문제

In the famous ICPC race, $n$ runners will participate. The course is $m$ kilometers long and for safety, it is divided into $m$ ranges. Each range is one kilometer long and Range $i$ (1ドル ≤ i ≤ m$) is the interval $(i - 1, i),ドル which is the section between $i - 1$ km and $i$ km from the starting point. We will ignore the case where the distance between the starting point and a runner is an integer. As the weather is quite hot, the organizers would like to put enough water. They will maintain a certain number of water bottles in each range. When a runner takes one bottle, they will put another immediately. They have found that the optimal number of water bottles could be obtained by calculating the maximum number of runners in that interval during the race. Based on the previous records of each runner, they have estimated how many seconds he/she will spend in each range.

Consider the following example. There are three runners, and the length of the course is six kilometers. The table shows the amount of time runners will spend in each range (in seconds).

Now we will check the number of runners in each range during the race. Intentionally, the table below is not complete. When you fill the whole table and compute the maximum number of runners for each range, you can see that you need to put three bottles of water in Range 1ドル,ドル two in Range 2ドル$ and Range 3ドル,ドル and one in Range 4ドル,ドル Range 5ドル,ドル and Range 6ドル$. Note that at 480ドル$s, Runner 2ドル$ leaves Range 2ドル$ and Runner 3ドル$ arrives at Range 2ドル,ドル both of which will be ignored as their distance from the starting point is an integer. At 480ドル$s, no runner is in Range 1ドル$ and in Range 3ドル$ and Runner 1ドル$ is in Range 2ドル$. Then, for example, at 481ドル$s, Runner 1ドル$ and Runner 3ドル$ will be in Range 2ドル$.

Given the number of runners, the length of the course, and the amount of time each runner will spend in each range, write a program to compute the number of bottles to be put in each range.

입력

Your program is to read from standard input. The input starts with a line containing two integers, $n$ and $m$ (1ドル ≤ n ≤ 100,ドル 1ドル ≤ m ≤ 300$), where $n$ is the number of runners and $m$ is the length of the course. In the following $n$ lines, the $i$-th line contains $m$ positive integers that represent the amount of time Runner $i$ will spend in each range. More precisely, the $j$-th number on the line is the time Runner $i$ will spend in Range $j$. No runner will spend more than 10ドル,000円$ seconds in any range.

출력

Your program is to write to standard output. Print exactly one line. The line should contain the numbers of bottles in each range from Range 1ドル$ to Range $m$.

제한

힌트