冰山 ### 题目描述 一片海域上有一些冰山，第 $i$ 座冰山的体积为 $V_i$。 随着气温的变化，冰山的体积可能增大或缩小。第 $i$ 天，每座冰山的变化量都是 $X_i$。当 $X_i > 0$ 时，所有冰山体积增加 $X_i$；当 $X_i < 0$ 时，所有冰山体积减少 $−X_i$；当 $X_i = 0$ 时，所有冰山体积不变。 如果第 $i$ 天某座冰山的体积变化后小于等于 $0$，则冰山会永远消失。 冰山有大小限制 $k$。如果第 $i$ 天某座冰山 $j$ 的体积变化后 $V_j$ 大于 $k$，则它会分裂成一个体积为 $k$ 的冰山和 $V_j − k$ 座体积为 $1$ 的冰山。 第 $i$ 天结束前（冰山增大、缩小、消失、分裂完成后），会漂来一座体积为 $Y_i$ 的冰山（$Y_i = 0$ 表示没有冰山漂来）。 小蓝在连续的 $m$ 天对这片海域进行了观察，并准确记录了冰山的变化。 小蓝想知道，每天结束时所有冰山的体积之和（包括新漂来的）是多少。 由于答案可能很大，请输出答案除以 $998244353$ 的余数。 ### 输入描述 输入的第一行包含三个整数 $n, m, k$，分别表示初始时冰山的数量、观察的天数以及冰山的大小限制。 第二行包含 $n$ 个整数 $V_1, V_2, \cdots , V_n$，表示初始时每座冰山的体积。 接下来 $m$ 行描述观察的 $m$ 天的冰山变化。其中第 $i$ 行包含两个整数 $X_i, Y_i$，意义如前所述。 ### 输出描述 输出 $m$ 行，每行包含一个整数，分别对应每天结束时所有冰山的体积之和除以 $998244353$ 的余数。 ### 输入输出样例 #### 示例 >输入 ```txt 1 3 6 1 6 1 2 2 -1 1 ``` >输出 ```txt 8 16 11 ``` ### 样例说明 在本样例说明中，用 $[a_1, a_2, \cdots , a_n]$ 来表示每座冰山的体积 初始时的冰山为 $[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 ≤ 2000$； 对于 $60$% 的评测用例，$n, m, k ≤ 20000$； 对于所有评测用例，$1 ≤ n, m ≤ 100000, 1 ≤ k ≤ 10^9 , 1 ≤ V_i ≤ k, 0 ≤ Y_i ≤ k,−k ≤ Xi ≤ k$。