题目背景

QAQ

题目描述

给定数列$a_1...a_n$及$x_0$。

满足

求

但这样太水了

于是给出$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$个数据点

保证$0 \le l\le r \le n$

想不到吧！