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.

【丛林】猩猩老师的能量考验

背景故事

在一片神奇的热带雨林中，住着一位智慧的猩猩老师。他掌管着一片神奇的香蕉园，每株香蕉树都蕴含着不同的能量值。猩猩老师不仅是丛林中最聪明的猩猩，更是一位深受尊敬的能量掌控大师。

一天，来自各个树冠的小猩猩学徒们齐聚在猩猩老师的香蕉园里学习。猩猩老师决定教给他们三种神奇的丛林能量技能：

1. "香蕉施肥术"：可以为一片区域的香蕉树注入能量
2. "能量统计术"：可以计算一片区域香蕉树的总能量
3. "巅峰探测术"：可以找出一片区域中能量最强的香蕉树

题目描述

作为一名见习小猩猩，你需要帮助猩猩老师老师完成这次教学。给定一排香蕉树的初始能量值，你需要处理以下三种技能：

1. 香蕉施肥：将区间 $[x, y]$ 内的每棵香蕉树增加 $k$ 点能量
2. 能量统计：计算区间 $[x, y]$ 内所有香蕉树的能量总和
3. 巅峰探测：找出区间 $[x, y]$ 内能量最高的香蕉树

输入格式

第一行包含两个整数 $n, m$，分别表示香蕉树的数量和技能施放的次数。

第二行包含 $n$ 个整数，表示每棵香蕉树的初始能量值。

接下来 $m$ 行，每行描述一次技能施放：

• 1 x y k：对区间 $[x, y]$ 的香蕉树使用施肥术，增加能量值 $k$
• 2 x y：对区间 $[x, y]$ 使用能量统计术
• 3 x y：对区间 $[x, y]$ 使用巅峰探测术

输出格式

对于每次能量统计术和巅峰探测术，输出一行结果。

提示

• 小猩猩的入门考验 (20%数据)：$n \leq 1000$，$m \leq 1000$
• 中级猩猩的进阶考验 (50%数据)：$n \leq 100000$，$m \leq 100000$
• 猩猩大师的提高考验 (65%数据)：$n \leq 100000$，$m \leq 100000$
• 猩猩牢师的终极考验 (100%数据)：$n \leq 200000$，$m \leq 200000$

注意：任何时刻香蕉园的总能量值不会超过 $10^{18}$，否则可能导致香蕉园能量过载！

祝你在猩猩老师的考验中取得优异成绩！

样例 #1

样例输入 #1

3 5
466 508 820
1 1 2 6
2 2 2
2 1 3
3 2 2
2 1 1

样例输出 #1

514
1806
514
472

样例 #2

样例输入 #2

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

样例输出 #1

5
8
20

样例故事

阿布老师正在教导五棵特别的香蕉树（初始能量值：1, 5, 4, 2, 3）。

1. 首先，他让学徒们统计第2到第4棵树的中最大能量树的能量值
2. 接着，他对第2到第3棵树施加了能量值为2的施肥术
3. 然后又统计了第3到第4棵树的能量
4. 最后，他对所有树都增加了1点能量
5. 再次统计了前4棵树的总能量

这个过程帮助小猩猩们理解了能量的变化和计算。