30925번 - Lucky Draws 2 다국어

문제

The ICPC committee is planning a surprise event to cheer on the participating teams. The committee provides each team with a pair of two numbers, $A$ and $B$ (1ドル ≤ A ≤ B ≤ m$), before the competition, which will be used for the lucky draws after the competition. The committee wants to hold $K$ draws. In each draw, a single number $C$ is chosen by the committee, and all teams with a pair $(A, B)$ such that $A ≤ C ≤ B$ win in this draw. To make more teams happy, the committee wants to choose the $K$ numbers used in the $K$ draws in advance so that the most teams win. A team can win multiple times but is considered to have won once.

For example, five teams are participating in ICPC and their pairs are $(1, 2),ドル $(1, 4),ドル $(3, 6),ドル $(4, 7),ドル $(5, 6),ドル and $K = 2$. When the committee chooses two numbers 2ドル$ and 4ドル$ , four teams with $(1, 2),ドル $(1, 4),ドル $(3, 6)$ and $(4, 7)$ win. The team with $(1, 4)$ wins twice because the pair contains both chosen numbers. In fact, all five teams can win if 2ドル$ and 5ドル$ are chosen. The maximum number of winning teams is five.

Given $n$ pairs of two integers for teams, write a program to output the maximum number of winning teams for all possible $K = 1, 2, \ldots, m$.

입력

Your program is to read from standard input. The input starts with a line containing two integers, $m$ and $n$ (1ドル ≤ m, n ≤ 1,000円,000円$), where $m$ is the upper bound of the numbers provided to teams and $n$ is the number of teams. Each of the following $n$ lines contains two integers $A$ and $B$ that represent the pair of a team, where 1ドル ≤ A ≤ B ≤ m$.

출력

Your program is to write to standard output. Print exactly $m$ lines. The $i$-th line should contain the maximum number of winning teams given that $K = i$. Teams that win more than once should only be counted once.

제한

힌트