P16255 [DSTOI Round 0] 白石溪

> 尘心如练 长悬银钩 > 鱼雁不闻 斯人难候 > 九霄一曲 人间白首 > 隔世相问 忆否忆否

白石溪畔，斜阳逐流。 这里有个长度为 $n$ 的序列 $a$（$\color{red}2\le n\le 8\times 10^4$）；有个正整数 $m$；还有 $k$ 对正整数 $(x_i,y_i)$（$\color{red}1\le k\le 4\times 10^4$），满足 $x_i

第一行三个正整数 $n,m,k$，含义见题目描述。 第二行 $n$ 个正整数，第 $i$ 个数为 $a_i$ 的初始值。 第 $3$ 到 $k+2$ 行，每行两个整数，第 $i+2$ 行（$i=1,2,\dots,k$）的两个数分别为 $x_i,y_i$ 的初值。 第 $k+3$ 行，一个自然数 $q$，代表修改次数。 接下来 $q$ 行，每行若干正整数，形如 `1 p x` 或 `2 M` 或 `3 p x' y'`，代表一次修改，含义见题目描述。

第一行一个自然数，代表第一次修改前，不同的 **「忆」** 的数量，对 $998244353$ 取模的结果。 第 $i+1$ 行（$i=1,2,\dots,q$）一个自然数，代表第 $i$ 次修改后，不同的 **「忆」** 的数量，对 $998244353$ 取模的结果。

**只有通过全部测试点，才能获得本题的分数。** ### 样例解释 \#1 初始 $a=[3,10,4,7,12]$，$m=12$，$(x_1,y_1)=(1,4)$，$(x_2,y_2)=(3,5)$。此时，唯一的 **「忆」** 为 $[(1,3),(4,5)]$。 第一次修改令 $(x_2,y_2)=(1,5)$，这时，有两个 **「忆」**：$[(1,3),(4,5)]$ 与 $[(1,2),(3,5)]$。 第二次修改令 $m=6$，此后出现了 $4$ 个 **「忆」**，分别是： - $[(1,2),(3,4),(5,5)]$； - $[(1,2),(3,5)]$； - $[(1,3),(4,4),(5,5)]$； - $[(1,3),(4,5)]$； 第三次修改令 $a_3=9$。可以证明不同的 **「忆」** 有 $6$ 个。 ### 数据范围 对初始状态与每次修改后，满足： $2\le n\le 8\times 10^4$，$1\le m\le 10^9$，$1\le k\le 4\times 10^4$，$0\le q\le 10^3$。 $1\le a_i\le 2.5\times 10^4$，$1\le x_i