#3526. Karin的弹幕

Karin的弹幕

Description

Karin在战斗之余的闲暇时光里喜欢上B站看鬼畜视频,尤其喜欢发弹幕。她这天对一个视频的弹幕产生了兴趣,她记录了每个时间点的弹幕数量,并且可能对一段呈等差数列的时间的弹幕数量求最大值;她还可能修改某个时间点的弹幕数量。

为了不在Yuuna面前暴露出她弱爆了的数学能力,保持她傲娇的属性,你需要帮助她。

精简题意:给定一个序列,支持以下操作:①对一段下标是等差数列的子序列进行求最大值操作(参见输入格式);②单点修改。

Format

Input

第一行是一个整数n,

第二行是一个长度为n的整数序列a1...an,

第三行是一个整数m,

接下来m行,每行首先有一个整数op,

然后,若op=0,则之后有两个整数p,v,代表将a[p]的值加上v,

若op=1,则之后有两个整数x0,d,代表询问max{a[x0],a[x0+d],a[x0+2d],...,a[x0+kd]}(x0+kd<=n,x0+(k+1)d>n)。

数据中可能有多余空格。

Output

对每个op=1,单独输出一行,代表该等差子序列的最大值。

Samples

【输入样例1】
10
1 6 1 4 9 4 8 2 8 5
10
1 3 3
0 5 4
0 3 8
1 2 5
1 4 8
1 7 5
1 3 6
0 1 2
1 5 3
1 4 9

【输入样例2】
10
-9 -6 2 -10 -2 -6 10 6 -4 -2
10
1 2 3
1 6 3
0 7 8
0 4 -6
0 10 -5
1 10 4
0 3 -8
1 2 4
0 10 -5
1 1 2
【输出样例1】
8
8
4
8
9
13
4

【输出样例2】
6
-4
-7
-6
18

Hint

【数据范围】

1<=n<=70000,

1<=m<=70000,

保证任何时刻abs(a[i])(1<=i<=n)<=2147483647,

0<=op<=1,

1<=p<=n,

abs(v)<=2147483647

1<=x0<=n,

1<=d<=n,

保证涉及的所有数在C++的int内。