Background

QAQ

Problem Description

Given a sequence $a_1 \ldots a_n$ and $x_0$.

It satisfies:

$$f[i][j]=\begin{cases} a_i & j=0,i<=n \\ x_0 & j=0,i=n+1 \\ f[i][j-1]+f[i-1][j-1] & 0<i,j<=n+1,j<i \\ 0 & i<=j \\ \end{cases}$$

Find:

$$\sum_{i=0}^{n+1}\sum_{j=0}^{n+1}f[i][j]$$

But this is too easy.

So $m$ operations are given. Each time, add $p$ to $a[l] \ldots a[r]$ $(0\le l,r \le n)$. For each operation, output the answer.

In particular, if $0$ is within the range $l \ldots r$, we consider that $x_0$ is also increased by $p$.

Also, before reading the $m$ operations, you should output the answer once.

Since the answer may be too large, output the result modulo $1234567891$.

Input Format

The first line contains two integers $n, m$.

The next line contains $n+1$ integers, which are $a_1 \ldots a_n$ and $x_0$, and the last one is $x_0$.

The next $m$ lines each contain $3$ integers $l, r, p$.

Output Format

There are $m+1$ lines in total. Each line contains one integer, the answer.

2 2
1 2 3
1 2 3
0 1 3

22
46
64

Hint

There are $20$ test points.

For the $i$-th test point:

$$n,m=\lfloor ln^{12}i+\pi^5\rfloor,|a,x,p|\le \lfloor ln^{19}i+i^{\pi}\rfloor$$

It is guaranteed that $0 \le l\le r \le n$.

Didn’t expect that, right!

Translated by ChatGPT 5