愈加善良的希望

【题目背景】

培训部的主管 Hod 陷入融毁，主管需要立刻对她进行核心抑制

【题目描述】

脑叶公司一共有 n 个员工，每个员工 i 有一个能力值 ai。

Hod 可以释放技能，使得一个区间 l，r 内的员工能力值发生变动，使得这些员工的能力值都 +k。

为了完成核心抑制，你需要回答主管的询问，每次主管想要派出前 k 名员工，给定 k 的范围 l ~ r，你需要回答主管 k 名员工的能力值之和最大是多少

【输入格式】

第一行一个整数 n 表示 n 个员工。

接下来一行 n 个整数 a1~n 表示每个员工的能力值。

接下来一行一个整数 q 表示 q 此询问

接下来 q 行表示 q 次操作，每次操作有两种情况

1 l r，表示一次查询。

0 l r k，表示一次修改。

【输出格式】

对于每一个操作 2，输出答案

【样例输入】

5
238 -9622 5181 202 -6943
5
1 3 4
0 5 5 4846
1 3 5
0 3 5 -7471
1 3 3

【样例输出】

-4001 
-4001 
-11674 

【样例说明】

大样例

pretest2 与测试点 3 ~ 6 范围一致

pretest3 与测试点 7 ~ 10 范围一致

【数据规模与约定】

对于前 20pts：n,q <= 1e3

对于另外的 40pts：所有的操作和修改满足 l = 1,r = n

对于 100% 的数据，满足 n,q <= 5e4，|a| <= 1e9,对于所有的操作，满足 |k| <= 1e4

【来源】

脑叶公司真好玩