演唱会(live)

小林最近迷上了参加演唱会，作为粉丝头子，小林要负责管理整个粉丝团队的应援活动。粉丝团队一共有 n 名粉丝在演唱会现场坐成一排，第 i 名粉丝的应援力度为 $a_i$ 。但是并不是每名粉丝的应援都很显眼，只有被聚光灯照射到时，粉丝们的应援才会被传达出来。

具体的，聚光灯每次会照射到一个区间 $[l,r]$ ，传达出的应援力度为区间中所有粉丝的应援力度之和乘以区间中最大的应援力度。同时，为了更好的应援，小林会通知某个粉丝更改他的应援力度，现在请你帮小林计算一下，每次聚光灯照射过来的时候，传达出的应援力度是多少?

第一行包含两个整数 $n,m$ ，表示一共有 n 名粉丝以及 m 次操作。

第二行包含n个整数，第 i 个数 $a_i$ 表示第i名粉丝的应援力度

接下来 m 行，每行一个操作符 $opt$ 。

当 $opt=1$ 时，输入两个正整数 $l,r$ ，表示聚光灯当前照射的区间为 $[l,r]$ ，查询当前区间中传达出的应援力度。

当 $opt=2$ 时，输入两个正整数 $x,y$ ，表示将第 x 名粉丝的应援力度修改为 $y$ 。

对于每个查询操作，输出 $[l,r]$ 区间中传达出的应援力度，

配套文件参看|ive2.in

配套文件参看live2.ans

对于 30%的数据， $1≤n,m≤1000。$

对于另外 2%的数据，保证所有 $opL=1$ 。

对于100%的数据， $1≤n,m<100000，$ $1<1,r,x≤n，1≤a_i,y<100000。$

#5714. 演唱会(live)