该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

小林最近迷上了参加演唱会，作为粉丝头子，小林要负责管理整个粉丝团队的应援活动。粉丝团队一共有 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]$ 区间中传达出的应援力度。

5 5
1 2 3 4 5
1 1 3
1 3 5
2 1 4
1 1 3
1 1 5

18
60
36
90

样例解释

操作 1：1 1 3 查询 [1, 3]

• 区间和：1 + 2 + 3 = 6
• 区间最大值：3
• 应援力度 = 6 × 3 = 18

输出：18

操作 2：1 3 5 查询 [3, 5]

• 区间和：3 + 4 + 5 = 12
• 区间最大值：5
• 应援力度 = 12 × 5 = 60

输出：60

操作 3：2 1 4 修改，将第 1 名粉丝的应援从 1 改为 4

操作 4：1 1 3 查询 [1, 3]

• 区间和：4 + 2 + 3 = 9
• 区间最大值：4
• 应援力度 = 9 × 4 = 36

输出：36

操作 5：1 1 5 查询 [1, 5]

• 区间和：4 + 2 + 3 + 4 + 5 = 18
• 区间最大值：5
• 应援力度 = 18 × 5 = 90

输出：90

样例2

数据范围与约定

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

对于另外 20% 的数据，保证所有 opt=1。

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