试题 G: 冰山

【问题描述】

一片海域上有一些冰山，第 i 座冰山的体积为 Vi。随着气温的变化，冰山的体积可能增大或缩小。第 i 天，每座冰山的变化量都是 Xi。当 Xi > 0 时，所有冰山体积增加 Xi；当 Xi < 0 时，所有冰山体积减少 −Xi；当 Xi = 0 时，所有冰山体积不变。如果第 i 天某座冰山的体积变化后小于等于 0，则冰山会永远消失。冰山有大小限制 k。如果第 i 天某座冰山 j 的体积变化后 Vj 大于 k，则它会分裂成一个体积为 k 的冰山和 Vj − k 座体积为 1 的冰山。第 i 天结束前（冰山增大、缩小、消失、分裂完成后），会漂来一座体积为Yi 的冰山（Yi = 0 表示没有冰山漂来）。小蓝在连续的 m 天对这片海域进行了观察，并准确记录了冰山的变化。小蓝想知道，每天结束时所有冰山的体积之和（包括新漂来的）是多少。由于答案可能很大，请输出答案除以 998244353 的余数。

【输入格式】

输入的第一行包含三个整数 n, m, k，分别表示初始时冰山的数量、观察的天数以及冰山的大小限制。

第二行包含 n 个整数 V1, V2, · · · , Vn，表示初始时每座冰山的体积。

接下来 m 行描述观察的 m 天的冰山变化。其中第 i 行包含两个整数 Xi, Yi，意义如前所述。

【输出格式】

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

【样例输入】

1 3 6

1

6 1

2 2

-1 1

【样例输出】

8

16

11

【样例说明】

在本样例说明中，用 [a1, a2, · · · , an] 来表示每座冰山的体积。

初始时的冰山为 [1]。 第 1 天结束时，有 3 座冰山：[1, 1, 6]。 第 2 天结束时，有 6 座冰山：[1, 1, 2, 3, 3, 6]。 第 3 天结束时，有 5 座冰山：[1, 1, 2, 2, 5]。