题目背景

父亲，您的王国在崩塌；

父亲，您的人民在离去；

父亲，但您说我不该有为苦难哭泣的声音；

所以我将无能为力，所以我独自分崩离析。

题目描述

容器面前有 $n$ 个感染者，这 $n$ 个感染者排成一列，编号依次从 $1$ 到 $n$，第 $i$ 个感染者的感染深度为 $a_i$。

容器会从第 $x$ 个感染者处开始向第 $n$ 个感染者走，依次经过第 $x$ 到 $n$ 个感染者。容器会击杀所有经过的感染者。然而，如果击杀了两个编号连续，感染深度严格递增的感染者，那么它会略过下一个感染者（如果存在下一个）。

记 $f_x$ 表示若容器从第 $x$ 个位置开始，击杀的感染者数量（$f$ 之间两两独立）。例如有五个感染者，他们的感染深度依次为：

2 6 4 5 1

那么对应的 $f$ 序列为 $\{4,3,2,2,1\}$。

你不知道每个感染者的感染深度，只知道 $m$ 组 $f_i-f_{i+1}$ 的值，对于请输出满足条件的不同 $f$ 序列的数量对 $998244353$ 取模的结果。

序列 $f,g$ 不同，当且仅当存在 $1\le i \le n$ 满足 $f_i\not= g_i$。

输入格式

第一行两个整数 $n,m$。

接下来 $m$ 行，每行一个二元组 $(x,y)$，表示 $f_x-f_{x+1}=y$。

注意，数据中可能存在错误的二元组，您需要自行忽略它们。具体地，若二元组 $(x_i,y_i)$ 使得考虑 $1\sim i-1$ 的所有合法二元组及该二元组后，不存在满足条件的 $f$ 序列，那么该二元组不合法，您在计算答案时不应考虑该二元组。

输出格式

输出为 $(m+1)$ 行，每行 $1$ 个数。

第一行表示不考虑任何二元组时的答案对 $998244353$ 取模的结果。

第 $i(2 \le i \le m+1)$ 行表示考虑 $1 \sim i-1$ 中所有合法二元组时的答案对 $998244353$ 取模的结果。

3 3
1 5
1 1
1 0

2
2
1
1

5 2
2 1
4 5

4
3
3

提示

样例一解释

初始：符合条件的 $f$ 序列有 $\{3,2,1\},\{2,2,1\}$。

约束一：初始的 $f$ 序列都不符合约束一，忽略该条件。

约束二：只有 $\{3,2,1\}$ 符合约束条件。

约束三：只有 $\{2,2,1\}$ 符合约束条件。结合约束二，不存在合法的 $f$ 序列，忽略该条件。

数据范围及约定

对于 $20\%$ 的数据，$n,m\le5$。

对于 $60\%$ 的数据，$n\le10^6$。

对于另外 $10\%$ 的数据，$m=0$。

对于 $100\%$ 的数据，$1 \leq n \leq 10^{11},0 \leq m \leq 5\times 10^4,0 \leq |y| \leq n,1 \leq x <n$。