Problem Description

In a sea area, there are some icebergs. The volume of the $i$-th iceberg is $V_{i}$.

As the temperature changes, the volume of the icebergs may increase or decrease. On day $i$, the change amount for every iceberg is $X_{i}$. When $X_{i} > 0$, the volume of all icebergs increases by $X_{i}$; when $X_{i} < 0$, the volume of all icebergs decreases by $-X_{i}$; when $X_{i} = 0$, the volume of all icebergs does not change.

If, after the change on day $i$, the volume of an iceberg becomes less than or equal to $0$, then the iceberg disappears forever.

There is a size limit $k$ for icebergs. If, after the change on day $i$, the volume $V_{j}$ of an iceberg $j$ is greater than $k$, then it will split into one iceberg of volume $k$ and $V_{j} - k$ icebergs of volume $1$.

Before the end of day $i$ (after the growth, shrinkage, disappearance, and splitting are all completed), one iceberg of volume $Y_{i}$ will drift in ($Y_{i} = 0$ means no iceberg drifts in).

Xiaolan observed this sea area for $m$ consecutive days and accurately recorded the changes of the icebergs. Xiaolan wants to know the total sum of volumes of all icebergs at the end of each day (including the newly drifted-in one).

Since the answer may be very large, please output the remainder when it is divided by $998244353$.

Input Format

The first line contains three integers $n, m, k$, representing the initial number of icebergs, the number of observed days, and the size limit of an iceberg.

The second line contains $n$ integers $V_{1}, V_{2}, \cdots, V_{n}$, representing the initial volume of each iceberg.

The next $m$ lines describe the iceberg changes for the $m$ observed days. The $i$-th line contains two integers $X_{i}, Y_{i}$, with meanings as described above.

Output Format

Output $m$ lines. Each line contains one integer, which is the remainder of the total sum of volumes of all icebergs at the end of that day divided by $998244353$.

1 3 6
1
6 1
2 2
-1 1

8
16
11

Hint

Sample Explanation

In this sample explanation, $\left[a_{1}, a_{2}, \cdots, a_{n}\right]$ is used to represent the volume of each iceberg.

Initially, the icebergs are $[1]$.

At the end of day $1$, there are $3$ icebergs: $[1,1,6]$.

At the end of day $2$, there are $6$ icebergs: $[1,1,2,3,3,6]$.

At the end of day $3$, there are $5$ icebergs: $[1,1,2,2,5]$.

Constraints and Conventions for Test Cases

For $40\%$ of the test cases, $n, m, k \leq 2000$.

For $60\%$ of the test cases, $n, m, k \leq 20000$.

For all test cases, $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$.

Lanqiao Cup 2021 National Contest Group A, Problem G.

Translated by ChatGPT 5