You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

吉利太美

题目背景

吉利实在是太美，多看一眼就会爆炸！

题目描述

吉利到底是有多美呢？这个我们也不知道，不过社长提出了一个美丽计算公式来描述吉利的美丽度。

我们将吉利学院的按照大小划分一个$n$行的矩阵$A$={$a_1,a_2,a_3,a_4,...,a_n$}，其中$a_i$代表第$i$位置的美丽度

不时，吉利学院会栽种一些树木使得$l$到$r$区间内的所有位置的美丽度同时增加$v(1<=v<=10^3)$。

同时吉利学院有可能会遭到不理智的“荔枝”破坏，使得$l$到$r$区间内的美丽清零。

为了能弄清各个时间内的吉利学院某个区间的美丽度，社长邀请你来完成这个任务，这个答案可能会很大，请输出结果并模$10^9+7$。

输入

第一行两个整数，$n$和$m$。分别表示吉利学院可以划分的大小以及操作次数。

第二行输入$n$个正数，{$a_1,a_2,a_3,a_4,...,a_n$}，其中$a_i$代表第$i$位置的干净度

接下来的$m$行每行输入3个整数k,l,r

当k=1时：接下来有三个正整数l,r,v。表示吉利学院的$l$ 到 $r$区间进行植树，对于区间所有位置的$a_i$干净度增加v。

当k=2时，接下来输入两个正整数，l,r。表示吉利学院的$l$ 到 $r$区间遭到了不理智的“荔枝”破坏，区间的美丽度清零。

当k=3时，接下来输入两个正整数，l,r。表示对你询问吉利学院的$l$ 到 $r$的美丽度。

输出

在k=3时，每行输出一个整数，表示查询的结果。

样例

输入1

10 5
1 2 3 4 5 6 7 8 9 10
3 1 5
2 1 5
3 1 5
1 1 5 10
3 1 5

15
0
50

样例说明

开始时，美丽度为：

1 2 3 4 5 6 7 8 9 10

使用2 1 5后，然后变成了

0 0 0 0 0 6 7 8 9 10

使用1 1 5 10后变成了

10 10 10 10 10 7 8 9 10

数据范围

$1<=n,m<=10^5$

$0<=a_i<=200$

$k=1/2/3$

$1<=l<=r<=n$

$-200<=v<=200$