AT_ndpc2026_q 区間の和集合

整数 $ M $ および $ N $ 個の整数の組 $ (L_1, R_1), \dots, (L_N, R_N) $ が与えられます。ここで任意の $ 1 \leq i \leq N $ を満たす整数 $ i $ について $ 1 \leq L_i \leq R_i \leq M $ が成り立ちます。 $ K = 1, 2, \dots, M $ に対して以下の問題の答えを求めてください。 > $ S \subseteq \lbrace 1, 2,\dots, N \rbrace $ である集合 $ S $ としてあり得るものは $ 2^N $ 通りありますが、そのうち以下の条件を満たすものは何個ありますか？答えを $ 998244353 $ で割った余りを求めてください。 > > - $ 1 $ 以上 $ M $ 以下の整数 $ m $ のうち、以下を満たすものがちょうど $ K $ 個である。 > - ある整数 $ i \in S $ が存在して、 $ L_i \leq m \leq R_i $ が成り立つ。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ L_1 $ $ R_1 $ $ L_2 $ $ R_2 $ $ \vdots $ $ L_N $ $ R_N $

$ M $ 行出力せよ。 $ i $ 行目には $ K=i $ の時の答えを出力せよ。

### 注意 この問題はメモリ制限が非常に厳しいです。 ### Sample Explanation 1 $ K=1 $ の時、条件を満たす $ S $ は $ 0 $ 個です。 $ K=2 $ の時、条件を満たす $ S $ は $ \lbrace 1 \rbrace, \lbrace 2 \rbrace $ の $ 2 $ 個です。 $ K=3 $ の時、条件を満たす $ S $ は $ \lbrace 3 \rbrace, \lbrace 2,3 \rbrace $ の $ 2 $ 個です。 $ K=4 $ の時、条件を満たす $ S $ は $ \lbrace 1,2 \rbrace, \lbrace 1,3 \rbrace, \lbrace 1,2,3 \rbrace $ の $ 3 $ 個です。 ### Constraints - $ 1 \leq N \leq 2000 $ - $ 1 \leq M \leq 4000 $ - $ 1 \leq L_i \leq R_i \leq M $ - 入力される値は全て整数