本题关于可满足性问题（SAT）的一个特殊情况。首先介绍 SAT 的定义。

SAT 实例是一个布尔逻辑公式，由若干布尔变量通过与（$\land$）、或（$\lor$）和非（$\neg$）运算符以及括号组合而成。赋值是将变量映射到布尔值的过程。如果一个赋值使得公式的计算结果为真，则称该赋值满足该公式。文字（literal）是变量或其否定。子句（clause）是由文字通过或运算连接而成的列表。如果一个公式由子句通过与运算连接而成，则称该公式为合取范式（CNF）。在下文中，我们仅考虑作为 SAT 输入的 CNF 公式，因为每个公式都可以转换为等价的 CNF 公式。

2-SAT 是 SAT 的一个特殊情况，其中子句的长度限制为 2。例如，$(x \lor y) \land (\neg x \lor z)$ 是一个包含 3 个变量和 2 个子句的 2-SAT 实例。赋值 $x = \text{false}, y = \text{true}, z = \text{true}$ 是该公式的满足赋值之一。

给定一个包含 $N$ 个变量和 $M$ 个子句的 CNF 形式的 2-SAT 实例。第 $i$ 个变量记为 $x_i$，其中 $i$ 称为其下标。在所有子句中，两个变量下标之差的绝对值小于或等于 2。

令 $C_k$ 为恰好有 $k$ 个变量为真的满足赋值的数量。你的任务是编写一个程序，计算所有 $k$ 从 $0$ 到 $N$ 的 $C_k$。由于答案可能非常大，请将其对 $998\,244\,353$ 取模。

输入格式

输入的第一行包含两个整数，变量的数量 $N$ ($1 \le N \le 100\,000$) 和子句的数量 $M$ ($1 \le M \le 100\,000$)。

接下来的 $M$ 行表示 2-SAT 实例中的子句。第 $i$ 行对应第 $i$ 个子句，包含两个整数 $A_i$ 和 $B_i$，表示该子句中的文字。它们满足 $1 \le |A_i|, |B_i| \le N$ 且 $||A_i| - |B_i|| \le 2$，每个整数的含义如下：如果是一个正整数 $a$，则文字为 $x_a$（无否定）；如果是一个负整数 $b$，则文字为 $\neg x_b$（有否定）。

输出格式

输出 $N+1$ 行。第 $i$ 行必须包含一个整数：$C_{i-1} \pmod{998\,244\,353}$ 的值。

样例

样例输入 1

4 2
1 -3
2 2

样例输出 1

0
1
2
2
1

样例输入 2

3 6
1 2
2 3
2 -1
1 3
2 -3
-2 3

样例输出 2

0
0
1
1