11248.演唱会（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]) 区间中传达出的应援力度。

• 对于 30% 的数据，1 ≤ ( n ), ( m ) ≤ 1000。
• 对于另外 20% 的数据，保证所有 ( opt = 1 )。
• 对于 100% 的数据，1 ≤ ( n ), ( m ) ≤ 100000，1 ≤ ( l ), ( r ), ( x ) ≤ ( n )，1 ≤ ( a_i ), ( y ) ≤ 100000。