小 $L$ 有 $n$ 条包含于 $[1,m]$ 的线段，其中第 $i$（$0 \le i < n$）条线段为 $[l_i,r_i]$（$1 \le l_i \le r_i \le m$）。

小 $L$ 认为过于复杂的线段相交关系不够优美。对于每一个线段集合 $S \subseteq \{0,1,\ldots,n-1\}$，小 $L$ 定义 $S$ 是 优美 的，当且仅当满足如下要求：

• 构造一个顶点集合与 $S$ 对应的图。顶点 $u$ 与顶点 $v$ 之间存在一条边，当且仅当线段 $u$ 与线段 $v$ 相交，即存在 $x \in [1,m]$，满足 $l_u \le x \le r_u$ 且 $l_v \le x \le r_v$。称 $S$ 是 优美 的，当且仅当构造出的图恰好为一棵树。

小 $L$ 想知道有多少线段集合是优美的，因此他给定了一个正整数 $k$（$k \le n$）。你需要计算，对于每个 $s = 1,2,\ldots,k$，有多少个大小为 $s$ 的集合是优美的。

由于答案可能较大，只需求出答案对 $998244353$ 取模后的结果。

实现细节

选手不需要，也不应该实现 main 函数。

选手需要确保提交的程序源文件包含头文件 segment.h，即在程序开头加入以下代码：

#include "segment.h"

选手需要在提交的程序源文件 segment.cpp 中实现以下两个函数：

void init(int c, int t);

• $c,t$ 分别表示测试点编号与测试数据组数。$c = 0$ 表示该测试点为样例。
• 对于每个测试点，该函数会在程序开始运行时被评测程序调用恰好一次。

std::vector<int> segment(int n, int m, int k, std::vector<int> l, std::vector<int> r);

• $n,m,k$ 分别表示线段的数量、坐标范围上限及需要计算的集合大小上限。
• $l,r$ 分别表示每条线段的左端点与右端点。
• 该函数需要返回一个长度恰好为 $k+1$ 的序列 $a$，其中 $a_0 = 0$，$a_s$（$1 \le s \le k$）表示大小为 $s$ 的优美集合数量对 $998244353$ 取模后的结果。
• 对于每个测试点，该函数会被评测程序调用恰好 $t$ 次。

本试题目录下的 template_segment.cpp 是提供的示例代码，选手可参考并实现自己的代码。

测试程序方式

选手可以在本题目录下使用如下命令编译得到可执行文件：

g++ grader.cpp segment.cpp -o segment -O2 -std=c++14 -static

对于编译得到的可执行文件 segment：

• 可执行文件将从标准输入读入以下格式的数据：
  • 第一行包含两个非负整数 $c,t$。
  • 接下来依次为每组测试数据。对于每组测试数据：
    • 第一行包含三个正整数 $n,m,k$。
    • 第 $i+2$（$0 \le i < n$）行包含两个正整数 $l_i,r_i$。
• 可执行文件将输出以下格式的数据至标准输出：
  • 对于每组测试数据，输出一行 $k$ 个非负整数 $a_1,a_2,\ldots,a_k$。

样例一

input

0 3
3 3 3
1 2
2 3
1 3
4 5 4
1 2
2 3
3 4
4 5
4 2 3
1 2
1 2
1 2
1 1

output

3 3 0
4 3 2 1
4 6 0

explanation

对于第一组测试数据：

• 大小为 $1$ 的集合有 $\{0\},\{1\},\{2\}$，均是优美的。
• 大小为 $2$ 的集合有 $\{0,1\},\{1,2\},\{0,2\}$，均是优美的。
• 大小为 $3$ 的集合有 $\{0,1,2\}$，构造出的图是一个三元环，不是优美的。

因此答案分别为 $3,3,0$。

对于第二组测试数据：

• 大小为 $1$ 的集合中，所有 $4$ 个集合均是优美的。
• 大小为 $2$ 的集合中，$\{0,1\},\{1,2\},\{2,3\}$ 是优美的。
• 大小为 $3$ 的集合中，$\{0,1,2\},\{1,2,3\}$ 是优美的。
• 大小为 $4$ 的集合 $\{0,1,2,3\}$ 是优美的。

因此答案分别为 $4,3,2,1$。

样例二

见下发文件 segment2.in/ans。

该样例满足测试点 $6 \sim 8$ 的约束条件。

样例三

见下发文件 segment3.in/ans。

该样例满足测试点 $9,10$ 的约束条件。

样例四

见下发文件 segment4.in/ans。

该样例满足测试点 $11 \sim 15$ 的约束条件。

样例五

见下发文件 segment5.in/ans。

该样例满足测试点 $16 \sim 18$ 的约束条件。

样例六

见下发文件 segment6.in/ans。

该样例满足测试点 $22,23$ 的约束条件。

样例七

见下发文件 segment7.in/ans。

该样例满足测试点 $24,25$ 的约束条件。

数据范围

设 $K$ 为单个测试点内所有测试数据的 $k$ 的和。

对于所有测试数据，均有：

• $1 \le t \le 20$；
• $1 \le n \le 3000$，$1 \le m \le 10^3$，$1 \le k \le n$，$K \le 200$；
• 对于所有 $0 \le i < n$，均有 $1 \le l_i \le r_i \le m$。

特殊性质 $A$：对于所有 $0 \le i,j < n$ 且 $i \ne j$，均有线段 $i$ 不包含线段 $j$，即 $l_i > l_j$ 或 $r_i < r_j$。

特殊性质 $B$：对于所有 $0 \le i < j < n$，均有线段 $i$ 包含线段 $j$，或线段 $i$ 与线段 $j$ 不相交，即 $l_i \le l_j \le r_j \le r_i$、$r_i < l_j$ 或 $l_i > r_j$。

特殊性质 $C$：$n$ 条线段的全部 $2n$ 个端点互不相同，即 $l_0,l_1,\ldots,l_{n-1},r_0,r_1,\ldots,r_{n-1}$ 两两不同。

时间限制：$\texttt{2.5s}$

空间限制：$\texttt{1024MB}$