AT_fps_24_u 録画機

We define the following as a **subproblem**: > There are $ N $ programs numbered $ 1 $ through $ N $ . Program $ i $ is broadcast from time $ A_i $ to time $ B_i $ . > You want to record all programs using $ 2 $ recorders. > > For a set of programs $ S $ , the condition that all programs in $ S $ can be recorded by a single recorder is that no two programs in $ S $ overlap in time. (It is acceptable if they only touch at the endpoints.) > > - More formally, all programs in $ S $ can be recorded if there are no distinct $ i, j \in S $ such that $ \max(A_i, A_j) < \min(B_i, B_j) $ holds. > > The question is whether it is possible to record all programs using $ 2 $ recorders. > More precisely, does there exist a partition $ S_1, S_2 $ of $ {1, 2, \dots, N} $ such that both $ S_1 $ and $ S_2 $ can each be recorded by a single recorder? > Output `Yes` if it is possible, otherwise output `No`. > > Constraints: > > - $ 0 \leq A_i < B_i \leq T $ > - $ N, T, A_i, B_i $ are integers You are given $ N $ and $ U $ . For each $ T = 1, 2, \dots, U $ , solve the following problem: - Suppose $ N, T $ are the same as in the subproblem. Then, the number of possible inputs $ (A_1, B_1), \dots, (A_N, B_N) $ is $ \left(\dfrac{T(T+1)}{2}\right)^N $ . Among them, count how many yield the answer `Yes` in the subproblem, and output the result modulo $ 998244353 $ .

The input is given from standard input in the following format: > $ N $ $ U $

Print $ U $ lines. On the $ i $ -th line, output the answer for $ T = i $ .

### Partial Score This problem has partial scoring: - If you solve all datasets with $ N \leq 5 \times 10^3 $ and $ U \leq 5 \times 10^3 $ , you will earn $ 4 $ points. ### Sample Explanation 1 For example, when $ T=2 $ , an input such as $ (A_1, B_1) = (0, 2) $ , $ (A_2, B_2) = (0, 1) $ , $ (A_3, B_3) = (1, 2) $ satisfies the condition. ### Constraints - $ 1 \leq N \leq 6 \times 10^4 $ - $ 1 \leq U \leq 6 \times 10^4 $ - $ N, U $ are integers