AT_abc418_f [ABC418F] We're teapots

有 $N$ 个茶壶排成一排，从左到右编号为 $1$ 到 $N$。 有一个整数序列 $(a_1, \dots, a_N)$，初始时 $a_1 = \dots = a_N = -1$。 你需要将每个茶壶装入茶或咖啡，使得以下所有条件都被满足： - 对于任意两个相邻的茶壶，至少有一个茶壶装的是茶。 - 对于任意满足 $1 \leq i \leq N$ 的整数 $i$，如果 $a_i \neq -1$，那么编号 $1$ 到 $i$ 的茶壶中恰好有 $a_i$ 个茶壶装的是咖啡。 你将会得到 $Q$ 个操作，请按顺序处理这些操作。 第 $j$ 个操作（$1 \leq j \leq Q$）如下： - 将 $a_{X_j}$ 的值修改为 $Y_j$。然后，输出满足条件的装填茶壶的方法数，对 $998244353$ 取模。

输入从标准输入读入，格式如下： > $N$ $Q$ > $X_1$ $Y_1$ > $\vdots$ > $X_Q$ $Y_Q$

输出 $Q$ 行。 第 $j$ 行（$1 \leq j \leq Q$）应输出第 $j$ 次操作后满足条件的方法数。

### 样例解释 1 - 第一次操作后，$a = (1, -1, -1, -1, -1)$。满足条件的装填方法共有五种： - 第 $1$ 个茶壶装咖啡，其余装茶。 - 第 $1, 3$ 个茶壶装咖啡，其余装茶。 - 第 $1, 3, 5$ 个茶壶装咖啡，其余装茶。 - 第 $1, 4$ 个茶壶装咖啡，其余装茶。 - 第 $1, 5$ 个茶壶装咖啡，其余装茶。 - 第二次操作后，$a = (1, -1, -1, 2, -1)$。满足条件的装填方法共有三种： - 第 $1, 3$ 个茶壶装咖啡，其余装茶。 - 第 $1, 3, 5$ 个茶壶装咖啡，其余装茶。 - 第 $1, 4$ 个茶壶装咖啡，其余装茶。 - 第三次操作后，$a = (0, -1, -1, 2, -1)$。满足条件的装填方法共有一种： - 第 $2, 4$ 个茶壶装咖啡，其余装茶。 - 第四次操作后，$a = (0, -1, -1, -1, -1)$。满足条件的装填方法共有八种： - 所有茶壶都装茶。 - 第 $2$ 个茶壶装咖啡，其余装茶。 - 第 $2, 4$ 个茶壶装咖啡，其余装茶。 - 第 $2, 5$ 个茶壶装咖啡，其余装茶。 - 第 $3$ 个茶壶装咖啡，其余装茶。 - 第 $3, 5$ 个茶壶装咖啡，其余装茶。 - 第 $4$ 个茶壶装咖啡，其余装茶。 - 第 $5$ 个茶壶装咖啡，其余装茶。 - 第五次操作后，$a = (0, -1, -1, -1, 1)$。满足条件的装填方法共有四种： - 第 $2$ 个茶壶装咖啡，其余装茶。 - 第 $3$ 个茶壶装咖啡，其余装茶。 - 第 $4$ 个茶壶装咖啡，其余装茶。 - 第 $5$ 个茶壶装咖啡，其余装茶。 - 第六次操作后，$a = (0, -1, -1, -1, 5)$。满足条件的方法数为零。 ### 数据范围 - $2 \leq N \leq 2 \times 10^5$ - $1 \leq Q \leq 2 \times 10^5$ - $1 \leq X_j \leq N$（$1 \leq j \leq Q$） - $-1 \leq Y_j \leq X_j$（$1 \leq j \leq Q$） - 所有输入均为整数。 由 ChatGPT 4.1 翻译