求和

QAQ

给定数列$a_1...a_n$及$x_0$。 满足 $$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}$$ 求 $$\sum_{i=0}^{n+1}\sum_{j=0}^{n+1}f[i][j]$$ ~~但这样太水了~~ 于是给出$m$个操作，每次将$a[l]...a[r] \ (0\le l,r \le n)$加$p$，对于每个操作，输出答案。 特别地，若$0$在$l...r$范围内，我们认为$x_0$也加$p$。 另外，在读入$m$个操作前，你也应该输出答案。 由于答案可能过大，输出答案对$1234567891$取模的结果。

第一行，两个整数$n,m$。 下面一行$n+1$个整数，为$a_1...a_n$及$x_0$，且最后一个是$x_0$。 下面$m$行，每行$3$个整数$l,r,p$。

共$m+1$行，每行一个整数，为答案。

2 2
1 2 3
1 2 3
0 1 3

22
46
64

共20个数据点。 对于第$i$个数据点 $$n,m=\lfloor ln^{12}i+\pi^5\rfloor,|a,x,p|\le \lfloor ln^{19}i+i^{\pi}\rfloor$$ 保证$0 \le l\le r \le n$ ~~想不到吧！~~