Question

Happy Sequence

Newton has A pairs of integers (X1, Y1), (X2, Y2), (X3, Y3),. . (Xa, Ya).

The value of both the integers in the pairs is between 1 and M (including 1 and B)

A happy sequence is defined as a contiguous subsequence of the sequence of all natural numbers from 1 to B (i. e. 1, 2, 3, 4,. M) and that the subsequence should contain atleast one integer from the A pairs.

Let F(x) define the number of possible happy subsequences of length x.

Find F(1), F(2),. . F(B).

The value of both the integers in the pairs is between 1 and M (including 1 and B)

A happy sequence is defined as a contiguous subsequence of the sequence of all natural numbers from 1 to B (i. e. 1, 2, 3, 4,. M) and that the subsequence should contain atleast one integer from the A pairs.

Let F(x) define the number of possible happy subsequences of length x.

Find F(1), F(2),. . F(B).

Input

The first line of the input consists of 2 integers A and B.

The next A lines contains 2 integers, X and Y

Constraints:

1 <= A <= 5×10^5

2 <= B <= 5×10^5

1 <= Xi < Yi <= B

The next A lines contains 2 integers, X and Y

Constraints:

1 <= A <= 5×10^5

2 <= B <= 5×10^5

1 <= Xi < Yi <= B

Output

Output consists of one line of integers seperated by space representing F(1), F(2),. . F(B)

Example

Sample Input:

3 5

1 3

1 4

2 5

Sample Output:

0 1 3 2 1

Explanation:

All possible happy sequences are given below:

(1, 2)

(1, 2, 3)

(2, 3, 4)

(3, 4, 5)

(1, 2, 3, 4)

(2, 3, 4, 5)

(1, 2, 3, 4, 5)

3 5

1 3

1 4

2 5

Sample Output:

0 1 3 2 1

Explanation:

All possible happy sequences are given below:

(1, 2)

(1, 2, 3)

(2, 3, 4)

(3, 4, 5)

(1, 2, 3, 4)

(2, 3, 4, 5)

(1, 2, 3, 4, 5)