{"raw_statement":[{"iden":"problem statement","content":"You are given an integer $M$ and $N$ pairs of integers $(A_1, B_1), (A_2, B_2), \\dots, (A_N, B_N)$.  \nFor all $i$, it holds that $1 \\leq A_i \\lt B_i \\leq M$.\nA sequence $S$ is said to be a **good sequence** if the following conditions are satisfied:\n\n*   $S$ is a contiguous subsequence of the sequence $(1,2,3,..., M)$.\n*   For all $i$, $S$ contains at least one of $A_i$ and $B_i$.\n\nLet $f(k)$ be the number of possible good sequences of length $k$.  \nEnumerate $f(1), f(2), \\dots, f(M)$."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 2 \\times 10^5$\n*   $2 \\leq M \\leq 2 \\times 10^5$\n*   $1 \\leq A_i \\lt B_i \\leq M$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $M$\n$A_1$ $B_1$\n$A_2$ $B_2$\n$\\vdots$\n$A_N$ $B_N$"},{"iden":"sample input 1","content":"3 5\n1 3\n1 4\n2 5"},{"iden":"sample output 1","content":"0 1 3 2 1\n\nHere is the list of all possible good sequences.\n\n*   $(1,2)$\n*   $(1,2,3)$\n*   $(2,3,4)$\n*   $(3,4,5)$\n*   $(1,2,3,4)$\n*   $(2,3,4,5)$\n*   $(1,2,3,4,5)$"},{"iden":"sample input 2","content":"1 2\n1 2"},{"iden":"sample output 2","content":"2 1"},{"iden":"sample input 3","content":"5 9\n1 5\n1 7\n5 6\n5 8\n2 6"},{"iden":"sample output 3","content":"0 0 1 2 4 4 3 2 1"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}