Seat Assignment for Children

There are \(n\) seats numbered from 1 to \(n\) from left to right. There are \(m\) children, and the \(i\)-th child can only sit on seats in the interval \([l_i, r_i]\). Each seat can hold at most one child.

Now, consider only the first \(k\) seats (i.e. seats 1 through \(k\)) and determine the maximum number of children that can be given a seat under these conditions. You are required to output the answer for every \(k\) from 1 to \(n\).

Input Format:
The first line contains two integers \(n\) and \(m\). Each of the following \(m\) lines contains two integers \(l\) and \(r\), representing that the corresponding child can sit on seats \(l, l+1, \ldots, r\).

Output Format:
Output \(n\) integers separated by spaces. The \(k\)-th integer is the maximum number of children who can be seated when only seats 1 to \(k\) are available.

Example:
For \(n = 3, m = 3\) and three children with intervals: \([2,2]\), \([2,3]\), \([1,3]\):

• \(k = 1\): One possible assignment is [Child with interval [1,3]] resulting in answer 1.
• \(k = 2\): One possible assignment is [Child with interval [1,3], Child with interval [2,3]] resulting in answer 2.
• \(k = 3\): One possible assignment is [Child with interval [1,3], Child with interval [2,2], Child with interval [2,3]] resulting in answer 3.

Thus, the output is: 1 2 3.

inputFormat

The first line contains two integers \(n\) and \(m\).
Each of the next \(m\) lines contains two integers \(l\) and \(r\), indicating that the corresponding child can sit in any seat in the interval \([l, r]\).

outputFormat

Output \(n\) integers separated by spaces. The \(k\)-th integer denotes the maximum number of children that can be seated when considering only seats 1 to \(k\).

sample

3 3
2 2
2 3
1 3

1 2 3