#1499. KC采花

KC采花

Description

KC在公园里种了一排花,一共有n朵,游手好闲的KC常常在公园里采花。他对每朵花都有一个美丽度鉴赏。由于对

花的喜好不同,有的花分数很高,有的花分数很低,甚至会是负数。KC很忙,每次采花的时候,不可能从第一朵花

,走到第n朵。所以他会先选定一个区间l,r,作为当天的采花范围。同时为了方便采花,他总是从

[l,r]中最多选出k个互不相交的子区间,将这些子区间的花全部采光。当然,他希望美丽度总和最大。KC对花的鉴

赏随着他对世界观人生观的改变而改变,他会不时地对每朵花的美丽度进行修改,可能改低,也可能提高。KC的行

为持续m天,每天的行为要么是采花,要么是改变花的美丽度。注:(1)[l,r]的最多k个互不相同子区间可以表示成

:[x1,y1],[x2,y2],...,[xt,yt],满足l<=x1<=y1<x2<=y2<...<xt<=yt<=r,且0<=t<=k。(2)由于是KC种的花,一

朵花采掉第二天会立刻生出来。

Format

Input

第一行一个正整数n,n<=100000。

第二行n个整数a1,a2...an,表示n朵花的美丽度。|ai|<=500。

第三行一个正整数m,m<=100000。

第四行开始,接下来m行,每行表示该天KC的行为。

修改美丽度的行为用0 i val描述,表示将ai修改为val,|val|<=500。

采花行为用1 l r k描述,k<=20意义如题面。

n,m<=50000,k<=20,ai以及修改的val的绝对值不超过500。

Output

对于每个采花行为,每行一个整数表示最大的美丽度总和

Samples

9
9 -8 9 -1 -1 -1 9 -8 9
3
1 1 9 1
1 1 9 2
1 4 6 3
17
25
0