#3272. Zgg吃东西

内存限制:256 MiB 时间限制:10 Sec

题目描述

Zgg是一个吃货。他面前有一堆的食品。不妨把它看成一个序列,序列从1~N编号,第i个位置上有美味度为A[i]的
食品。Zgg有很多只手(为什么他有这么多手?我也不知道)。他的手的作用,就是抓起一段连续序列中的食物,并
且不限长度。总共有M个时刻,在每个时刻,可能会有一些奇怪的人将他面前的某一个位置的食物美味度改变。或
者zgg突然心血来潮,想要用他的其中k只手来抓取某段区间中的食物。这时候,他就需要你告诉他,在用不超过k
只手的情况下,他能获得的最大美味度是多少。

输入格式

第一行一个整数N,表示食品的个数,即序列长度。
第2行有N个数依次表示A[i]。
第三行一个整数M,表示有M个时刻。
接下来的M行,每行有形如0 i val来表示有人将第i位置的食物的美味度改成了val
或者1 l r k,来表示zgg想知道,他只用k只手,在[l,r]这段区间内抓取,能获得的最大美味度。
N,M<=100000 ,1<=k<=20.l<=l<=r<=n.数值的绝对值不会超过500.
Zgg是可以有手空闲的…

输出格式

对于每次形如1 l r k的询问你都要输出一个数,表示最大美味度。

样例

样例输入


			
9
9 -8 9 -1 -1 -1 9 -8 9
5
1 1 9 1
1 1 9 2
1 4 6 3
0 3 -8
1 1 9 1

样例输出


			
17
25
0
10

数据范围与提示