容器面前有 $n$ 个感染者，这 $n$ 个感染者排成一列，编号依次从 $1$ 到 $n$，第 $i$ 个感染者的感染深度为 $a_i$。
容器会从第 $x$ 个感染者处开始向第 $n$ 个感染者走，依次经过第 $x$ 到 $n$ 个感染者。容器会击杀所有经过的感染者。然而，如果击杀了两个**编号连续，感染深度严格递增**的感染者，那么它会略过下一个感染者（如果存在下一个）。
记 $f_x$ 表示若容器从第 $x$ 个位置开始，击杀的感染者数量（$f$ 之间两两独立）。例如有五个感染者，他们的感染深度依次为：
```plain
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$。
## Input
第一行两个整数 $n,m$。
接下来 $m$ 行，每行一个二元组 $(x,y)$，表示 $f_x-f_{x+1}=y$。
注意，数据中可能存在错误的二元组，您需要自行忽略它们。具体地，若二元组 $(x_i,y_i)$ 使得考虑 $1\sim i-1$ 的所有合法二元组及该二元组后，不存在满足条件的 $f$ 序列，那么该二元组不合法，您在计算答案时不应考虑该二元组。
## Output
输出为 $(m+1)$ 行，每行 $1$ 个数。
第一行表示不考虑任何二元组时的答案对 $998244353$ 取模的结果。
第 $i(2 \le i \le m+1)$ 行表示考虑 $1 \sim i-1$ 中所有合法二元组时的答案对 $998244353$ 取模的结果。
[samples]
## Background
父亲，您的王国在崩塌；
父亲，您的人民在离去；
父亲，但您说我不该有为苦难哭泣的声音；
所以我将无能为力，所以我独自分崩离析。
## Note
### 样例一解释
初始：符合条件的 $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$。