AT_ndpc2026_q.Union of Intervals

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$.

给你一个整数 $M$ 和 $N$ 对整数 $(L_1, R_1), \dots, (L_N, R_N)$。对每个 $i$（$1 \leq i \leq N$），满足 $1 \leq L_i \leq R_i \leq M$。

对每个 $K = 1, 2, \dots, M$，求解以下问题：

共有 $2^N$ 个可能的子集 $S \subseteq \lbrace 1,2,\dots,N\rbrace$。其中，有多少个子集 $S$ 满足如下条件？将答案对 $998244353$ 取模后输出。

• 满足如下条件的整数 $m$（$1 \leq m \leq M$）的个数恰好为 $K$：
  • 存在某个整数 $i \in S$，使得 $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$

输入从标准输入中按以下格式给出：

$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$.

输出 $M$ 行。在第 $i$ 行中，输出 $K = i$ 时的答案。

Note

This problem has a very strict memory limit.

Sample 1 Explanation:
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

注意

本题的内存限制非常严格。

样例 1 解释：
当 $K=1$ 时，满足条件的子集 $S$ 有 $0$ 个。
当 $K=2$ 时，满足条件的子集有 $2$ 个：$\lbrace 1\rbrace , \lbrace 2\rbrace$。
当 $K=3$ 时，满足条件的子集有 $2$ 个：$\lbrace 3\rbrace , \lbrace 2,3\rbrace$。
当 $K=4$ 时，满足条件的子集有 $3$ 个：$\lbrace 1,2\rbrace , \lbrace 1,3\rbrace , \lbrace 1,2,3\rbrace$。

限制条件

• $1 \leq N \leq 2000$
• $1 \leq M \leq 4000$
• $1 \leq L_i \leq R_i \leq M$
• 所有输入值均为整数