Expected Sum on a Probabilistic Segment Tree

In this problem, DreamMei arranged a sequence of stars into a segment tree. The tree maintains the sum of weights in each interval. At a leaf node the weight is simply the star's weight and at an internal node it is the sum of its two children. DreamMei then takes a probabilistic journey from the root toward a leaf: At any internal node with left‐child interval sum \(sum_l\) and right–child interval sum \(sum_r\) (with total \(sum_{cur}=sum_l+sum_r\)), she goes to the left child with probability \(\frac{sum_l}{sum_{cur}}\) and to the right child with probability \(\frac{sum_r}{sum_{cur}}\). As she traverses the tree she accumulates the weight of every node she visits. Her journey’s total accumulated weight is a random variable, and she is interested in its expected value.

Moreover, DreamMei may issue instructions that update the weights of some stars. Each instruction is in the form of adding a constant value \(v\) to every star whose index is in the interval \([l, r]\). After every update the entire segment tree is updated immediately (i.e. without lazy propagation) and the journey’s expected total weight is recalculated.

The segment tree is constructed as follows: The leaves correspond to the initial array of star weights \(a[1\ldots n]\) and each internal node covers an interval which is split roughly in half. For a leaf node, the expected value is just its weight. For an internal node covering \([l,r]\) with children covering \([l,mid]\) and \([mid+1,r]\), let the sums be \(S_l\) and \(S_r\) respectively and let the expected values be \(F_l\) and \(F_r\). Then the expected value \(F_{[l,r]}\) of this node is calculated as \[ F_{[l,r]} = (S_l+S_r) + \frac{F_l\cdot S_l + F_r\cdot S_r}{S_l+S_r}, \] where all operations (including division) are done modulo \(MOD=998244353\). (Recall that when doing division modulo \(MOD\), you should multiply by the modular inverse.)

Your task is to process \(q\) update queries. The input initially contains \(n\), the number of stars, and \(q\). The second line contains \(n\) integers representing the initial star weights. Each of the following \(q\) lines contains three integers \(l\), \(r\), \(v\) meaning that you should add \(v\) (modulo \(998244353\)) to each star with index in \([l, r]\). After each update, output the expected total accumulated weight from the root of the segment tree (i.e. the value computed for the entire interval \([1,n]\)).

Note. If the sum of weights in an interval is 0, then the expected value for that interval is defined to be 0.

inputFormat

The first line contains two integers \(n\) and \(q\) \( (1 \leq n, q \leq 5000) \), representing the number of stars and the number of queries.

The second line contains \(n\) integers: \(a_1, a_2, \ldots, a_n\) \( (0 \leq a_i < 998244353)\) representing the initial star weights.

Then \(q\) lines follow. Each line contains three integers \(l, r, v\) \( (1 \leq l \leq r \leq n, 0 \leq v < 998244353)\), representing an update: add \(v\) to each star in index range \([l, r]\).

outputFormat

After each update query, output one line containing a single integer, the expected accumulated weight (modulo \(998244353\)) when DreamMei starts her probabilistic journey from the root of the segment tree.

sample

3 3
1 2 3
1 2 1
2 3 2
1 3 1

6
8
10