Iceberg Dynamics

A sea region is populated with several icebergs. The volume of the i-th iceberg is \(V_{i}\). Over a period of \(m\) days, the volumes of all icebergs change and new icebergs drift in.

On day \(i\), every iceberg's volume changes by \(X_{i}\):

• If \(X_{i} > 0\), each iceberg increases in volume by \(X_{i}\).
• If \(X_{i} < 0\), each iceberg decreases in volume by \(-X_{i}\).
• If \(X_{i} = 0\), no change occurs.

Immediately after the change:

• If an iceberg's volume becomes \(\le 0\), it disappears permanently.
• If an iceberg's volume becomes greater than a given limit \(k\), it splits into two parts:
  • One iceberg of volume \(k\), and
  • \(V - k\) icebergs each of volume \(1\) (where \(V\) is the current volume after change).

Then, before the day ends (after all changes and splitting), an additional iceberg with volume \(Y_{i}\) drifts in. (Note: \(Y_{i} = 0\) means no iceberg drifts in.)

Your task is to determine, for each day, the sum of the volumes of all icebergs at the end of the day (after all modifications and the drifting in of the new iceberg). Since the answer can be large, output it modulo \(998244353\).

Input Format:

The first line contains three integers \(n\), \(m\), and \(k\) where \(n\) is the number of initial icebergs, \(m\) is the number of days, and \(k\) is the splitting volume limit.

The second line contains \(n\) integers: \(V_{1}, V_{2}, \dots, V_{n}\) representing the initial volumes of the icebergs.

Then, \(m\) lines follow. The \(i\)-th of these lines contains two integers \(X_{i}\) and \(Y_{i}\) describing the change in volume on day \(i\) and the volume of the iceberg that drifts in at the end of day \(i\), respectively.

Output Format:

Output \(m\) lines. The \(i\)-th line should contain a single integer representing the total volume of all icebergs at the end of day \(i\), modulo \(998244353\).

inputFormat

The first line contains three integers n, m, and k.\nThe second line contains n integers representing the initial volumes of the icebergs.\nThen m lines follow, each containing two integers X_i and Y_i.

outputFormat

Output m lines, each containing the sum of the volumes of all icebergs at the end of the corresponding day modulo 998244353.

sample

3 3 5
3 6 1
-2 4
3 0
-1 2

9
18
9

</p>