Summation of Custom Recursive Table

You are given a sequence \(a_1,a_2,\dots,a_n\) and an extra integer \(x_0\). These values are used to build a table \(f[0\dots n+1][0\dots n+1]\) defined as follows:

[ f[i][j]=\begin{cases} a_i, & j=0,; 1\le i\le n,\ x_0, & j=0,; i=n+1,\ f[i][j-1] + f[i-1][j-1], & 1\le j\le n+1,; j < i,\ 0, & \text{if } i\le j. \end{cases} ]

Your task is to compute the sum

[ S=\sum_{i=0}^{n+1}\sum_{j=0}^{n+1} f[i][j] \pmod{1234567891}. ]

After the initial input, you are given \(m\) update operations. Each operation is described by three integers \(l, r, p\) (with \(0\le l\le r\le n\)). In each operation, you must add \(p\) to every element in the range \(a[l]\) through \(a[r]\). (Note that the positions of the \(n+1\) numbers are labeled from \(0\) to \(n\); here index \(0\) corresponds to \(x_0\) and indices \(1\) to \(n\) correspond to \(a_1,\dots,a_n\).) In particular, if \(0\) lies in the interval \([l,r]\) then \(x_0\) is also incremented by \(p\).

You should output the answer modulo \(1234567891\) before any update operations and then after each update.

Hint: It turns out that the overall answer is a linear function in the base values. In fact, one may show that

[ S = \sum_{k=1}^{n} a_k \cdot \Bigl({n+2 \choose k} - 1\Bigr) + x_0 \cdot \Bigl({n+2 \choose n+1} - 1\Bigr) \pmod{1234567891}, ]

since \({n+2 \choose n+1} = n+2\) the coefficient for \(x_0\) is \(n+1\). Use this formula together with precomputation of binomial coefficients (modulo \(1234567891\)) to answer the queries efficiently.

inputFormat

The first line of input contains two integers \(n\) and \(m\) (the length of the sequence and the number of update operations).

The second line contains \(n+1\) integers. The first \(n\) numbers represent \(a_1,a_2,\dots,a_n\) and the last number is \(x_0\).

Then \(m\) lines follow. Each line contains three integers \(l\), \(r\) and \(p\), representing an update operation: add \(p\) to each element from index \(l\) to index \(r\) (both inclusive). (Remember: index \(0\) corresponds to \(x_0\) and indices \(1\) to \(n\) correspond to \(a_1\) to \(a_n\).)

outputFormat

Output \(m+1\) lines. The first line is the answer (\(S\) modulo \(1234567891\)) computed from the initial input, and each of the next \(m\) lines is the answer after performing each update operation in order.

sample

1 2
2 3
0 0 1
1 1 2

10
12
16

</p>