P8767 [蓝桥杯 2021 国 A] 冰山

一片海域上有一些冰山，第 $i$ 座冰山的体积为 $V_{i}$ 。 随着气温的变化，冰山的体积可能增大或缩小。第 $i$ 天, 每座冰山的变化量都是 $X_{i}$。当 $X_{i}>0$ 时，所有冰山体积增加 $X_{i}$；当 $X_{i}

输入的第一行包含三个整数 $n, m, k$, 分别表示初始时冰山的数量、观察的天数以及冰山的大小限制。 第二行包含 $n$ 个整数 $V_{1}, V_{2}, \cdots, V_{n}$，表示初始时每座冰山的体积。 接下来 $m$ 行描述观察的 $m$ 天的冰山变化。其中第 $i$ 行包含两个整数 $X_{i}, Y_{i}$，意义如前所述。

输出 $m$ 行，每行包含一个整数，分别对应每天结束时所有冰山的体积之和除以 $998244353$ 的余数。

**【样例说明】** 在本样例说明中，用 $\left[a_{1}, a_{2}, \cdots, a_{n}\right]$ 来表示每座冰山的体积。 初始时的冰山为 $[1]$。 第 $1$ 天结束时，有 $3$ 座冰山：$[1,1,6]$。 第 $2$ 天结束时，有 $6$ 座冰山：$[1,1,2,3,3,6]$。 第 $3$ 天结束时，有 $5$ 座冰山：$[1,1,2,2,5]$。 **【评测用例规模与约定】** 对于 $40 \%$ 的评测用例，$n, m, k \leq 2000$; 对于 $60 \%$ 的评测用例，$n, m, k \leq 20000$; 对于所有评测用例，$1 \leq n, m \leq 10^5,1 \leq k \leq 10^{9}, 1 \leq V_{i} \leq k, 0 \leq Y_{i} \leq k, -k \leq X_{i} \leq k$。 蓝桥杯 2021 国赛 A 组 G 题。