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)