AT_ndpc2026_q 区間の和集合

You are given an integer $ M $ and $ N $ pairs of integers $ (L_1, R_1), \dots, (L_N, R_N) $ . For each $ i $ ( $ 1 \leq i \leq N $ ), it holds that $ 1 \leq L_i \leq R_i \leq M $ . For each $ K = 1, 2, \dots, M $ , solve the following problem: > There are $ 2^N $ possible subsets $ S \subseteq \lbrace 1,2,\dots,N\rbrace $ . Among them, how many satisfy the following condition? Output the answer modulo $ 998244353 $ . > > - The number of integers $ m $ ( $ 1 \leq m \leq M $ ) satisfying the following condition is exactly $ K $ : > - There exists an integer $ i \in S $ such that $ L_i \leq m \leq R_i $ .

The input is given from standard input in the following format: > $ N $ $ M $ $ L_1 $ $ R_1 $ $ L_2 $ $ R_2 $ $ \vdots $ $ L_N $ $ R_N $

Print $ M $ lines. On the $ i $ -th line, output the answer for $ K = i $ .

### Note This problem has a very strict memory limit. ### Sample Explanation 1 When $ K=1 $ , there are $ 0 $ subsets $ S $ that satisfy the condition. When $ K=2 $ , there are $ 2 $ such subsets: $ \lbrace 1\rbrace , \lbrace 2\rbrace $ . When $ K=3 $ , there are $ 2 $ such subsets: $ \lbrace 3\rbrace , \lbrace 2,3\rbrace $ . When $ K=4 $ , there are $ 3 $ such subsets: $ \lbrace 1,2\rbrace , \lbrace 1,3\rbrace , \lbrace 1,2,3\rbrace $ . ### Constraints - $ 1 \leq N \leq 2000 $ - $ 1 \leq M \leq 4000 $ - $ 1 \leq L_i \leq R_i \leq M $ - All input values are integers